題目鏈接：點擊查看

題目大意：給出兩個字符串s1和s2，求出s1的前綴和s2的后綴可以匹配的最大長度，并輸出其匹配的子字符串

題目分析：因為涉及到了前后綴的關系，我想的是可以將s1和s2連接成一個字符串s，然后對于s求一下next數組，一下就能知道前后綴匹配的最大長度了，只不過有點細節需要注意，next[n]最大肯定是不能超過s1和s2中長度較小的那個值，所以當next[n]的長度大于上面提到的最小值的話，我們就需要繼續迭代，直到滿足條件再輸出

需要注意的是，開cin加速外掛后一定不能再用scanf和printf了！！！

2019年11月5日更新：

這個題其實不用那么麻煩，只需要在合并字符串a和字符串b的時候，中間加一個#就可以防止中間會有重疊的地方了，更新代碼放到下面：

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef unsigned long long ull;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;string s1,s2,s;int nx[N];void getnext() {nx[0]=-1;int i=0,j=-1;while(i<s.size()){if(j==-1||s[i]==s[j])nx[++i]=++j;elsej=nx[j];} }int main() { // freopen("input.txt","r",stdin);ios::sync_with_stdio(false);while(cin>>s1>>s2){s=s1+s2;getnext();int len=min(s1.size(),s2.size());if(nx[s.size()]==0)cout<<0<<endl;else{int pos=nx[s.size()];while(pos>len)pos=nx[pos];string ans=s.substr(0,pos);cout<<ans<<' '<<pos<<endl;}}return 0; }

更新版：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef unsigned long long ull;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;string s1,s2,s;int nx[N];void getnext() {nx[0]=-1;int i=0,j=-1;while(i<s.size()){if(j==-1||s[i]==s[j])nx[++i]=++j;elsej=nx[j];} }int main() { // freopen("input.txt","r",stdin);ios::sync_with_stdio(false);while(cin>>s1>>s2){s=s1+"#"+s2;getnext();string ans=s.substr(0,nx[s.size()]);if(ans.size())cout<<ans<<' '<<ans.size()<<endl;elsecout<<0<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 2594 Simpsons’ Hidden Talents(KMP的next数组)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。