給出兩個(gè)字符串（可能包含空格）,找出其中最長的公共連續(xù)子串,輸出其長度。

注意這里是找連續(xù)子串。

算法：動(dòng)態(tài)規(guī)劃。f[i][j]表示第一個(gè)字符串前i個(gè)字符中與第二個(gè)字符串前j個(gè)中的最長連續(xù)子串長度

那么狀態(tài)轉(zhuǎn)移為：當(dāng)s1(i)==s2(j)時(shí)，f[i][j]=max(f[i][j],f[i-1][j-1]+1).不等時(shí)則為0；

#include<iostream> #include<algorithm> #include<vector> using namespace std; int main(void){int ans=0;string s1,s2;getline(cin,s1);getline(cin,s2);int n=s1.size(),m=s2.size();s1=" "+s1;s2=" "+s2;vector<vector<int>>f(n+1,vector<int>(m+1,0));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(s1[i]==s2[j]){f[i][j]=f[i-1][j-1]+1;ans=max(ans,f[i][j]);}else f[i][j]=0;}cout<<ans<<endl;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/programyang/p/11152220.html

總結(jié)

以上是生活随笔為你收集整理的最长公共连续子串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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