題目鏈接：點(diǎn)擊查看

題目大意：給出一個字符串 s 和一個暴力程序，用于求解 s 的每個后綴和原字符串的最長公共前綴，現(xiàn)在問一共需要執(zhí)行多少次比較操作

題目分析：首先肯定不能暴力去模擬，時間復(fù)雜度n*n，也不能用后綴數(shù)組，這個題好像特地卡了后綴數(shù)組的時間，倍增法nlogn會被卡掉，DC3因?yàn)槌?shù)太大也會被卡掉，網(wǎng)上說AC自動機(jī)會被卡內(nèi)存，因?yàn)檎麄€字符集是ASCII碼的范圍，那就只能用擴(kuò)展KMP來求解了，擴(kuò)展KMP在O(n)時間內(nèi)求解出extend[ i ]數(shù)組，表示字符串 s 的每個后綴和字符串 t 匹配的最長公共前綴，這樣一來就和這個題目對應(yīng)上了，將字符串 t 的位置替換上字符串 s 就是答案了，記得特判一下每次匹配是否匹配到末尾，如果不是末尾需要加一，因?yàn)樽詈竽谴纹ヅ涫∫菜阋淮纹ヅ洳僮?/p>

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;char s[N];LL Next[N],extend[N];//預(yù)處理計算Next數(shù)組 void getNext(char str[]) {int i=0,j,po,len=strlen(str);Next[0]=len; //初始化Next[0]while(str[i]==str[i+1] && i+1<len) i++; Next[1]=i; //計算Next[1]po=1; //初始化po的位置for(i=2;i<len;i++){if(Next[i-po]+i < Next[po]+po) //第一種情況，可以直接得到Next[i]的值Next[i]=Next[i-po];else //第二種情況，要繼續(xù)匹配才能得到Next[i]的值{j = Next[po]+po-i;if(j<0) j=0; //如果i>po+Next[po],則要從頭開始匹配while(i+j<len && str[j]==str[j+i]) j++; Next[i]=j;po=i; //更新po的位置}} }//計算extend數(shù)組 void EXKMP(char s1[],char s2[]) {int i=0,j,po,len=strlen(s1),l2=strlen(s2);getNext(s2); //計算子串的Next數(shù)組while(s1[i]==s2[i] && i<l2 && i<len) i++; extend[0]=i;po=0; //初始化po的位置for(i=1;i<len;i++){if(Next[i-po]+i < extend[po]+po) //第一種情況，直接可以得到extend[i]的值extend[i]=Next[i-po];else //第二種情況，要繼續(xù)匹配才能得到extend[i]的值{j = extend[po]+po-i;if(j<0) j=0; //如果i>extend[po]+po則要從頭開始匹配while(i+j<len && j<l2 && s1[j+i]==s2[j]) j++; extend[i]=j;po=i; //更新po的位置}} }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%s",s);int n=strlen(s);getNext(s);EXKMP(s,s);LL ans=0;for(int i=1;i<n;i++)ans+=extend[i]+(extend[i]!=n-i);printf("%lld\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 6629 string matching(扩展KMP)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。