本题很有问题...

Solution

网上用 Hash 大部分都是如下步骤：

• 不带*hash 判不同
• 带*判前后缀
• 带*和不带*暴力匹配（可以 hash/kmp）

在第三步的时候，可能会出现最坏 $O(Tn|S|_{max})$ 的情况，因此是复杂度错误的解。

以下程序可以提供 hack 数据：

#include<bits/stdc++.h>
using namespace std;

int main() {
    freopen("in","w",stdout);
    ios::sync_with_stdio(false), cin.tie(0);
    cout<<10<<endl;
    for(int i=0;i<10;i++) {
        int n=100000;
        cout<<n<<endl;
        for(int i=0;i<n-1;i++) cout<<"*b*"<<endl;
        for(int i=0;i<1999;i++) cout<<'a';
        cout<<'b'<<endl;
    }
    return 0;
}

然而网上的题解并没有找到更好的解法（我找到的都被卡了）

loj 的前二都能通过此数据

由于发现这个问题的时候已经打了一半了所以顺手打完了（顺便复习了 KMP）所以干脆将错就错了...

希望有能人士能给出复杂度正确的题解，非常感谢

常数过大导致无法通过 loj 的第四组数据。

Code

// Code by ajcxsu
// Problem: kazu

#include<bits/stdc++.h>
using namespace std;

vector<string> ps, ls, str;
const int mo[]={1000000007, 1000000009};
pair<int, int> ghash(string x) {
    int a=0, b=0;
    for(auto it=x.begin(); it!=x.end(); it++) a=(1ll*a*50+*it)%mo[0], b=(1ll*b*50+*it)%mo[1];
    return make_pair(a, b);
}
string tmp; pair<int, int> ha;
bool cmp(const string &a, const string &b) { return a.size()>b.size(); }

vector<int> nex;
int find(string s, string t, int pos) {
    nex.clear();
    int lens=s.size(), lent=t.size(), t1=0, t2=-1;
    nex.push_back(-1);
    while(t1<lent) {
        if(t2==-1 || t[t1]==t[t2]) nex.push_back(++t2), ++t1;
        else t2=nex[t2];
    }
    int i=pos, j=0;
    while(i<lens) {
        if(j==-1 || s[i]==t[j]) i++, j++;
        else j=nex[j];
        if(j==lent) return i-lent;
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t; cin>>t;
    while(t--) {
        int n; cin>>n;
        string s;
        vector<string>().swap(ps), vector<string>().swap(ls), vector<string>().swap(str);
        tmp="", ha.first=-1;
        int f, l;
        bool ok=1;
        for(int i=0;i<n;i++) {
            cin>>s;
            f=s.find('*');
            if(f!=-1) {
                l=s.rfind('*');
                if(f) ps.push_back(s.substr(0, f));
                if(s.size()-l-1) ls.push_back(s.substr(l+1, s.size()-l-1));
                str.push_back(s);
            }
            else if(ha.first==-1) ha=ghash(s), tmp=s;
            else if(ghash(s)!=ha) ok=0;
        }
        if(!ok) { cout<<'N'<<endl; continue; }
        sort(ps.begin(), ps.end(), cmp);
        sort(ls.begin(), ls.end(), cmp);
        if(ps.size())
        for(int i=0; i<ps[0].size(); i++) {
            for(int j=1; j<ps.size(); j++)
                ok&=(i>=ps[j].size() || ps[j][i]==ps[0][i]);
        }
        for(int j=0; j<ls.size(); j++) reverse(ls[j].begin(), ls[j].end());
        if(ls.size())
        for(int i=0; i<ls[0].size(); i++) {
            for(int j=1; j<ls.size(); j++)
                ok&=(i>=ls[j].size() || ls[j][i]==ls[0][i]);
        }
        if(!ok) { cout<<'N'<<endl; continue; }
        if(ha.first!=-1) {
            int ap, bp, np;
            for(int i=0; i<str.size(); i++) {
                ap=bp=0;
                while(1) {
                    np=str[i].find('*', ap);
                    if(np==ap) { ap=np+1; continue; }
                    else if(np==-1) break;
                    bp=find(tmp, str[i].substr(ap, np-ap), bp);
                    ap=np+1;
                    if(bp==-1) { ok=0; break; }
                    bp++;
                }
                np=str[i].size();
                if(ap!=np) {
                    bp=find(tmp, str[i].substr(ap, np-ap), bp);
                    if(bp==-1) { ok=0; break; }
                }
            }
        }
        if(!ok) cout<<"N"<<endl;
        else cout<<"Y"<<endl;
    }
    return 0;
}