50% 思路是计算比较最长公共子串的长度 #include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; //是否存在子串 int findLongestSize(string A, string B, int&endindex) { int n=A.size(); int m=B.size(); vector<vector<int> > matrix(n,vector<int>(m,0)); int res=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(A.at(i)==B.at(j)) { if(i==0||j==0) matrix[i][j]=1; else matrix[i][j]=matrix[i-1][j-1]+1; if(res<matrix[i][j]) { res=matrix[i][j]; endindex=i; } } } } return res; } int main() { string line; //string x="nihao"; //cout<<x.substr(3); string a,b; string output4[4]={"invalid","forward","backward","both"}; while(cin>>line) { int res=0;//0-invalid 3both cin>>a>>b; if(a.size()+b.size()>line.size()) { cout<<output4[res]<<endl; continue; } //isforward int lcs1=0; int lcs2=0; int endindex=0; lcs1=findLongestSize(line,a,endindex); if(line.size()-endindex>b.size()) { lcs2=findLongestSize(line.substr(endindex+1),b,endindex); if(lcs1+lcs2==a.size()+b.size()) res=1; } //isbackward string rline=line; reverse(rline.begin(),rline.end()); int lcs3=0; int lcs4=0; endindex=0; lcs3=findLongestSize(rline,a,endindex); if(rline.size()-endindex>b.size()) { lcs4=findLongestSize(line.substr(endindex+1),b,endindex); if(lcs3+lcs4==a.size()+b.size()) { if(res) res=3; else res=2; } } cout<<output4[res]<<endl; } return 0; }