字符串匹配问题
有n个a串个m个b串,讲a的前缀和b的后缀粘在一起有多少个不同的新串。
首先求不同的前缀和后缀肯定好求了,就用字典树分别存一下a个倒过来的b。
那个问题就是解决例如,abcd,和bcde为ab串,abcde为新串的去重问题,可以看出来有四 个重复,a bcde,ab cde, abc de, abcd e,我们能够很轻易的观察到如果两串的前缀后缀的重和部分(在这里即为bcd)有n个,那个会有n+1种重复,所以只要减掉那些重合的部分就好,用字典树记录有多少以a结尾的长度大于1的前缀,和以a开头的长度大于一的后缀(这里a指任意字母),相乘就是需要减掉的部分。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<iostream> #include<string.h> #include<stdio.h> using namespace std; #include<iostream> #include<string.h> #include<stdio.h> #include<algorithm> #include<queue> using namespace std; const int maxa = 500000; const int cha = 26; int n, m, k; long long num[100][2]; struct Tire{ int next[maxa][cha], fail[maxa], end[maxa]; int root, L; int newnode(){ for(int i = 0;i < 26; i++){ next[L][i] = -1; } end[L++] = 0; //printf("%d ", L); return L-1; } void init(){ L = 0; root = newnode(); } void insert(char buf[], int node){///printf("%s ", buf); int len = strlen(buf); int now = root; for(int i = 0; i < len; i++){ if(next[now][buf[i] - 'a'] == -1){ next[now][buf[i]-'a'] = newnode(); num[buf[i] - 'a'][node] ++; if(now == 0) num[buf[i] - 'a'][node] --; } now = next[now][buf[i]-'a']; } } }ac, ac1; char str[1000999]; int main(){ int n, m; while(scanf("%d%d", &n, &m), n+m){ memset(num, 0, sizeof(num)); ac.init();ac1.init(); for(int i = 0;i < n; i++){ scanf("%s", str); ac.insert(str, 0); } for(int k = 0; k < m; k++){ scanf("%s", str); reverse(str, str+strlen(str)); ac1.insert(str, 1); } long long ans = (long long)(ac1.L-1)* (ac.L-1); //cout<<ans<<endl; for(int i = 0;i < 26; i++){ ans -= num[i][0]*num[i][1]; } cout<<ans<<endl; } } /* 1 1 aaaa aaaa */