题目大意：
给定一个目标串$t(|t|le10^7)$和$m(mle10^5)$个模板串$s_i(|s_i|le100)$，对于每个$s_i$，求$s_i$在$t$中出现过的最长前缀。
思路：
先用所有的$s_i$建一个AC自动机，然后将$t$放进去匹配，标记经过的所有结点及其失配指针指向的结点。再将每个$s_i$放进去匹配，找到最深的有标记的位置。
1 #include<list> 2 #include<queue> 3 #include<cstdio> 4 #include<cctype> 5 #include<cstring> 6 inline int getint() { 7 register char ch; 8 while(!isdigit(ch=getchar())); 9 register int x=ch^'0'; 10 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 11 return x; 12 } 13 const int L1=1e7+1,M=1e5,L2=101,S=4; 14 char t[L1],s[M][L2]; 15 class AhoCorasick { 16 private: 17 std::queue<int> q; 18 bool val[M*L2],vis[M*L2]; 19 int ch[M*L2][S],fail[M*L2]; 20 int sz,new_node() { 21 return ++sz; 22 } 23 int idx(const char &c) const { 24 if(c=='N') return 0; 25 if(c=='E') return 1; 26 if(c=='W') return 2; 27 if(c=='S') return 3; 28 } 29 public: 30 void insert(const char s[]) { 31 for(register int i=0,p=0;s[i];i++) { 32 const int c=idx(s[i]); 33 p=ch[p][c]?:ch[p][c]=new_node(); 34 } 35 } 36 void get_fail() { 37 for(register int c=0;c<S;c++) { 38 if(ch[0][c]) q.push(ch[0][c]); 39 } 40 while(!q.empty()) { 41 const int &x=q.front(); 42 for(register int c=0;c<S;c++) { 43 int &y=ch[x][c]; 44 if(y) q.push(y); 45 (y?fail[y]:y)=ch[fail[x]][c]; 46 } 47 q.pop(); 48 } 49 } 50 void find(const char s[]) { 51 for(register int i=0,p=0;s[i];i++) { 52 for(register int q=p=ch[p][idx(s[i])];!vis[q];q=fail[q]) { 53 val[q]=vis[q]=true; 54 } 55 } 56 } 57 int query(const char s[]) { 58 for(register int i=0,p=0;s[i];i++) { 59 if(!val[p=ch[p][idx(s[i])]]) return i; 60 } 61 return strlen(s); 62 } 63 }; 64 AhoCorasick ac; 65 int main() { 66 const int n=getint(),m=getint(); 67 scanf("%s",t); 68 for(register int i=0;i<m;i++) { 69 scanf("%s",s[i]); 70 ac.insert(s[i]); 71 } 72 ac.get_fail(); 73 ac.find(t); 74 for(register int i=0;i<m;i++) { 75 printf("%d ",ac.query(s[i])); 76 } 77 return 0; 78 }