这个题。。需要对KMP的模板理解的比较透彻,以前我也只是会套模板。。后来才知道。。之会套模板是不行的。。如果不能把握模板的每一个细节`,至少能搞清楚模板的每一个模块大体是什么意思。。
题意是给出两个串,用这两个串组成一个新串,使新串包含这两个串,问这个新串的长度最小是多少,显然,对于两个串A,B,A如果是B的字串或者B如果是A的字串的话,直接输出那个母串的长度即可,如果没有这种关系,那么看一个串的后缀是否是另一个串的前缀,如果某个串的后缀与另一个串的前缀的公共部分最长,则答案=A.length+B.length-公共长度。
用到两次KMP,分别用A匹配B,以及用B匹配A,取min值;
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<map> #include<vector> #include<cmath> #include<set> using namespace std; const int maxn = 1e6+5; char p[maxn],t[maxn]; int find_sub(char *pattern,char *text) { int n = strlen(pattern); vector<int> next(n+1,0); for(int i = 1; i < n; ++i) { int j = i; while(j > 0){ j = next[j]; if(pattern[j] == pattern[i]){ next[i+1] = j+1; break; } } } int m = strlen(text),i,j; for(i = 0, j = 0; i < m; ++i) { if(j < n&&text[i] == pattern[j]) j++; else{ while(j > 0){ j = next[j]; if(text[i] == pattern[j]) { j++; break; } } } if(j == n) return m;//模式串匹配到了终点,说明文本串包含模式串,返回文本串长度; //if(i == m) return pattern.length()+text.length()-j; } if(i == m) return m+n-j;//文本串走到了终点,说明文本串后缀与模式串前缀有重叠;总长度=A+B-公共部分 return m+n; } int main() { //freopen("in","r",stdin); int T; scanf("%d",&T); while(T--) { scanf("%s%s",p,t); int ans = min(find_sub(p,t),find_sub(t,p)); cout<<ans<<endl; } }