一个串
找出字符串的最长子串,要求字串的所有字符相同,如:”abcdeeefgh”结果是”eee”
解题:
public class TestStr { public static void main(String args[]){ String s = "abcdeeefgh"; String result = ""; int count = 0; int max = count; int i,j; for(i = 0; i < s.length(); i++){ for(j = i + 1; j < s.length(); j++){ if(s.charAt(i) == s.charAt(j)){ count++; } else break; } if(count > max){ max = count; result = s.substring(i,j); } count = 0; } System.out.println(result); } }
两个串
两个字符串的最长子串
解题:
#include <iostream> using namespace std; const int N = 1000; char* FirstMaxSubString(const char *str1,char *str2) { int pos; //存放第一个最长子串的起始位置 int max = 0; //第一个最长子串的长度 int i,j; for(i=0;str1[i];i++) { for(j=0;str2[j];j++) { for(int k=0;str1[i+k]==str2[j+k] && (str1[i+k] || str2[i+k]);k++) if(k>max) { pos = j; max = k+1; } } } char *result = new char[max+1]; for(i=0;i<max;i++) result[i] = str2[pos++]; result[i] = '/0'; return result; //或者直接用下面的语句返回,好处是不用申请空间 /*str2[pos+max] = '/0'; return (char *)(str2+pos);*/ } int main() { char *str1 = new char[N]; char *str2 = new char[N]; cout<<"string_1:"; cin.getline(str1,N); cout<<"string_2:"; cin.getline(str2,N); //固定测试例 /* char *str1 = "abractyeyt"; char *str2 = "dgdsaeactyey"; */ cout<<"FirstMaxSubString:"<<FirstMaxSubString(str1,str2)<<endl; return 0; }
动态规划:
char str1[]="abractyeyt"; char str2[]="dgdsaeactyey"; #define N sizeof(str1)-2 #define W sizeof(str2)-2 int path[N][W]; int sum=0; int t=0; int begin; int LCS_2(char *str1,char *str2,int len1,int len2) { if(len1<=0||len2<=0) return 0; else { for(int i=0;i<len1;i++) { for(int j=0;j<len2;j++) { if(str1[i]==str2[j]) { path[i+1][j+1]=path[i][j]+1; } else { path[i+1][j+1]=0; } if(path[i+1][j+1]>sum) { begin=i-sum; sum=path[i+1][j+1]; } } } } return sum; } int LCS_1(char *str1,char *str2,int len1,int len2) { if(len1<=0||len2<=0) return 0; for(int i=1;i<=len1;i++) { for(int j=1;j<=len2;j++) { // if(*(str1+i-1)==*(str2+j-1)) if(str1[i-1]==str2[j-1]) { path[i][j]=path[i-1][j-1]+1; } else { path[i][j]=0; } if(path[i][j]>=sum) sum=path[i][j]; } } return sum; } int LCS(char *str1,char *str2,int len1,int len2) { if(len1<=0||len2<=0) return 0; for(int i=0;i<len1;i++) { for(int j=0;j<len2;j++) { if(*(str1+len1-1)==*(str2+len2-1)) { path[len1-1][len2-1]=1; return LCS(str1,str2,len1-1,len2-1)+1; } else { int a=LCS(str1,str2,len1,len2-1); int b=LCS(str1,str2,len1-1,len2); if(a>b) { path[len1-1][len2-1]=2; } else path[len1-1][len2-1]=-1; return a>b?a:b; } } } } void Print_1(int m) { int i=0; while(i<m) { cout<<*(str1+begin+i++); } } void Print() { std::stack<char> st; //for(int i=0;i<=N;i++) //{ // for(int j=0;j<=W;j++) // cout<<path[i][j]<<" "; // cout<<endl; //} //cout<<endl; int i=N,j=W; while(i>=0&&j>=0) { if(path[i][j]==-1) { i=i-1; } else if(path[i][j]==1) { st.push(str2[j]); i--; j--; } else j=j-1; } while(!st.empty()) { cout<<st.top(); st.pop(); } cout<<endl; } int main() { int m=LCS_2(str1,str2,strlen(str1),strlen(str2)); cout<<m<<endl; Print_1(m); cout<<endl; cout<<LCS(str1,str2,strlen(str1),strlen(str2))<<endl; Print(); return 0; }
首先祝博主元宵节快乐!
另想问一下博主能不能交换友链呢?我们的QQ是293459572,如果博主有这种想法可以和我们联系。
虽然看不懂,但感觉很专业~~~~