最长公共连续子串

	#include <iostream>



	using namespace std;



	 



	/*思路：假设两个字符串str1和str2，长度分别为m和n，则构建一个m*n的矩阵matrix，



	       matrix[i][j]==1表示字符串str1中第i个字符与str2中第j个字符相等，为0则不相等。



	       统计矩阵matrix中每条斜线上1的连续最大个数就是str1和str2中公共连续子串的最大长度*/



	/*例如：str1: abcde    str2: abgde 



	      matrix = [ 1  0  0  0  0 



	                 0  1  0  0  0



	                 0  0  0  0  0



	                 0  0  0  1  0



	                 0  0  0  0  1 ]



	    斜线上连续的1的最大个数为2，所以最长公共连续子串长度为2*/



	 



	intmain()



	{



	    charstr1[51];



	    charstr2[51];



	    intleng, maxleng=0;



	    cin.getline(str1, 51);



	    cin.getline(str2, 51);



	    intmatrix[50][50] = { 0};              //构建初始矩阵matrix



	 



	    for(inti = 0; str1[i] != '\0'; i++)            



	    {



	        for(intj = 0; str2[j] != '\0'; j++)



	        {



	            if(str1[i] == str2[j])



	                matrix[i][j] = 1;                     //如果str1中第i个字符与str2中第j个字符相等，则为1



	        }



	    }



	 



	    //循环统计每条斜线上的连续1的个数



	    for(inti = 0; str1[i]!='\0'; i++)          



	    {



	        for(intj = 0; str2[j]!='\0'; j++)



	        {



	            leng = 0;



	            intm = i;



	            intn = j;



	            while(matrix[m++][n++] == 1)          //判断其右下角位置是否为1



	                leng++;



	            if(maxleng < leng)



	                maxleng = leng;



	        }



	    }



	    cout << maxleng;



	         



	    return0;



	}

#include <stdio.h>
#include <string.h>
#define N 50
int main(){
    char s1[N],s2[N];
    int dp[N][N],i,j,max_len=0;
    gets(s1);
    gets(s2);
    for(i=0;i<strlen(s1);i++){
    	for(j=0;j<strlen(s2);j++){
    		if(s1[i]==s2[j]){
		    	if(i>0&&j>0){
	    			dp[i][j]=dp[i-1][j-1]+1;
	    		}else{
		    		dp[i][j]=1;
		    	}
		    	if(max_len<dp[i][j]){
	    			max_len=dp[i][j];
	    		}
		    }
	    }
    }
    printf("%d\n",max_len);
	return 0;
} 

import java.util.Scanner;

public class Main 
{
	
	public static void main(String[] args) 
	{
		Scanner scanner = new Scanner(System.in);
		String str1 = scanner.nextLine();
		String str2 = scanner.nextLine();
		scanner.close();
		
		//字符串的长度
		int n1 = str1.length();
		int n2 = str2.length();
		
		//边界情况
		if(n1 < 1 || n2 < 1)
		{
			System.out.println(0);
			return;
		}
		//利用空间存储两个串的比较结果，空间换时间
		int temp[][] = new int[n1][n2];
		//表示最长的公共字串的变量
		int longest = 0;
		char[] char1 = str1.toCharArray();
		char[] char2 = str2.toCharArray();
		
		//初始化数组temp
		for(int i = 0; i < n1; i++)
		{
			for(int j = 0;j <n2;j++)
			{
				temp[i][j] = 0;
			}
		}
		
		//初始化第一行，初始化第一列，因为状态转移公式：item[i][j]=1 +item[i-1][j-1]
		for(int i = 0;i < n1;i++)
		{
			if(char1[i] == char2[0])
				temp[i][0] = 1;
		}
		
		for(int i = 0;i < n2;i++)
		{
			if(char1[0] == char2[i])
				temp[0][i] = 1;
		}
		
		
		//利用状态转移方程进行填充temp二维数组
		for(int i = 1; i < n1;i++)
		{
			for(int j = 1; j<n2;j++)
			{
				if (char1[i] == char2[j]) 
				{
					temp[i][j] = temp[i-1][j-1] +1;
				}
			}
		}
		
		for(int i = 0; i < n1;i++)
		{
			for(int j = 0; j<n2;j++)
			{
				if(temp[i][j] > longest)
					longest = temp[i][j];
			}
		}
		
		System.out.println(longest);
	}
}

#include<iostream>
#include <string.h>
using namespace std;

int getMax(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    int ret = 0;
    char ch1[50];
    char ch2[50];
    cin.getline(ch1,50);
    cin.getline(ch2,50);
    
    for(int i = 0;i<strlen(ch1);i++)
    {
        int n = 0;
        for(int j =0;j<strlen(ch2);j++)
        {
            if(ch1[i+n] == ch2[j])
            {
                n++;
                ret = getMax(ret,n);
                continue;
            }
            else
                n=0;
        }
        
    }
    
    cout << ret;
}

二维动态规划，改成一维了，假设已经找到最长公共子串，并且子串最后一个字符对应于
s1、s2的第i、j个字符，那么dp[i][j]就是最终结果。
dp[i][j]表示以s1第i个字符、s2第j个字符为结尾的最长公共子串长度，
dp[i][j] = dp[i-1][j-1] + k(if(s[i] == s[j],k = 1否则k = 0)
缩小空间复杂度的一种简单方法是dp[i%2][j] = dp[(i-1)%2][j]，直接写成二维的程序
然后无脑加上模运算
import java.util.*;
public class Main{
	public static void main(String[] arg){
		 Scanner sc = new Scanner(System.in);
	     char[] s1 = sc.nextLine().toCharArray(), s2 = sc.nextLine().toCharArray();
	     int max = 0;
	     int[] dp = new int[s2.length+1];
	     dp[0] = 0;
	     for(int i = 0; i < s1.length; ++i){
	    	 for(int j = dp.length-1; j >= 1; --j){
	    		 if(s1[i] == s2[j-1])	dp[j] = dp[j-1] + 1;
	    		 else	dp[j] = 0;
	    		 if(dp[j]> max)	max = dp[j];
	    	 }
	     }
	     System.out.println(max);
	}
}

	a=raw_input()



	b=raw_input()



	ct=[]



	s=0



	fl=0



	iflen(a)==1and len(b)!=1:



	    fl=1



	    fori in b:



	        ifa==i:



	            print 1



	        else:



	            print 0



	iflen(b)==1:



	    fl=1



	    fori in a:



	        ifb==i:



	            print 1



	        else:



	            print 0   



	 



	fori in range(len(a)-1):   



	    forj in range(len(b)-1):       



	        ifa[i]==b[j] and a[i+1]==b[j+1]:



	            s=s+1



	            break



	        elif a[i]==b[j]:



	            ct.append(s)



	            s=0



	ct.append(s)



	ifmax(ct)!=0:



	     



	    print max(ct)+1



	else:



	    iffl==0:



	        print 0

import java.util.Scanner;

public class LongestSubstring {
	public static void main (String args[]){
		Scanner scanner=new Scanner(System.in);
		String str1=scanner.nextLine();
		String str2=scanner.nextLine();
		int max=0;
		System.out.print(longestSubstring(str1,str2));
	}
	public static int longestSubstring(String str1,String str2){
		if(str1.length()==0||str2.length()==0) return 0;
		int max=0;
		for(int i=1;i<=str1.length();i++){
			for(int j=i;j<=str1.length();j++){
				StringBuffer sb1=new StringBuffer(str1.substring(i-1,j));
				System.out.println(sb1);
				if(str2.contains(sb1)){
					if(sb1.length()>=max) max=sb1.length();
				}

			}
		}
		return max;
	}

import java.util.Scanner;

public class Main {
    public int findLength(String s1, String s2) {
        char[] A = s1.toCharArray();
        char[] B = s2.toCharArray();
        int n = A.length;
        int m = B.length;
        int[][] dp = new int[n + 1][m + 1];
        int res = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    res = Math.max(res, dp[i][j]);
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String s1=cin.nextLine();
        String s2 = cin.nextLine();
        System.out.println(new Main().findLength(s1,s2));
    }
}
/*
abcde
abgde
2

asdfas
werasdfaswer
 6
 */

import sys
 
try:
    while True:
        a = input()
        b = input()
        lm = len(a)
        ln = len(b)
        if lm >= ln:
            m = b
            n = a
            l = ln
        else:
            m = a
            n = b
            l = lm
        x = 0
        y = 0
        for i in range(l):
            for j in range(l,i,-1):
                if m[i:j] in n:
                    y = len(m[i:j])
                    break
            if x < y:
                x = y
        print(x)
except:
    pass

list1=list(input())
list2=list(input())
list1_tmp=[]
list2_tmp=[]
for i in range(len(list1)):
    tmp=""
    for j in range(i,len(list1)):
        tmp=tmp+list1[j]
        list1_tmp.append(tmp)
for i in range(len(list2)):
    tmp=""
    for j in range(i,len(list2)):
        tmp=tmp+list2[j]
        list2_tmp.append(tmp)
L=[]
for i in list1_tmp:
    if i in list2_tmp:
        if len(i)>len(L):
            L=i
print(len(L))

import sys
lines1 = raw_input()
line2 = raw_input()
lines = [lines1,line2]
length1 = len(lines[0])
length2 = len(lines[1])
matrix = [[0]* length2 for i in range(length1)]
for i in range(len(lines[0])):
    for j in range(len(lines[1])):
        if lines[0][i] == lines[1][j]:
            matrix[i][j] = 1
maxCount = 0
for i in range(len(lines[0])):
    for j in range(len(lines[1])):
        count = 0
        while  i < len(lines[0]) and j < len(lines[1]) and matrix[i][j] == 1:
            count += 1
            i += 1
            j += 1
        maxCount = max(maxCount,count)
print maxCount

 #include <iostream> #include <string.h>  using namespace std; int dp[50][50]={0}; int LCS2(const string &a,const string &b,int n,int m)
{
    memset(dp[0],0,sizeof(dp[0])); for(int i=0;i<50;i++)
    {
        dp[i][0]=0;
    } int max=0; for(int i=1;i<=n;i++)
    { for(int j=1;j<=m;j++)
        { if(a[i-1]==b[j-1])
            {
                dp[i][j] = dp[i-1][j-1]+1; if(dp[i][j]>max)
                    max = dp[i][j];
            } else  {
                dp[i][j] = 0;
            }
        }
    } return max;
} int main()
{ string a,b; while(getline(cin,a))
    {
        getline(cin,b);
        cout<<LCS2(a,b,a.length(),b.length())<<endl;
    } return 0;
}

#include <iostream>
#include <cmath>
#include <string>
using namespace std;

int findmax(string a,string b,int m,int n){
    int k=0,l=0;
    for(int i=0;i<a.length()-m && i<b.length()-n;i++){
            if(a[m+i]==b[n+i])  k++;
            else{
                if(k>l) l=k;
                k=0;
                return l;
            }
    }
    return k;
}
int main(int argc, const char * argv[]) {
    string a,b;
    getline(cin,a);
    getline(cin,b);
    int m=0,n=0;
    string temp;
    if(a.length()>b.length()){
        temp = a;
        a = b;
        b = temp;
    }
    for(int i =0;i<a.length();i++){
        for(int j=0;j<b.length();j++){
            if(a[i]==b[j]){
                m = findmax(a, b, i, j);
                if(m>n){
                    n=m;
                }
            }
        }
    }
    cout<<n;
    return 0;
}

public static int maxLenghtOfPublicString(String str1, String str2) {
    if (str1.length() == 0 || str2.length() == 0) {
        return 0;
    }
    int maxLength = 0;
    int len1 = str1.length();
    int len2 = str2.length();
    int[] matrix = new int [len1 * len2];
    int i, j;
    // 计算数组
    for (i = 0; i < len1; i++) {
        String s1 = str1.substring(i, i + 1);
        for (j = 0; j < len2; j++) {
            String s2 = str2.substring(j, j + 1);
            int index = i + j * len1;
            int value = s1.equals(s2) ? 1 : 0;
            matrix[index] = value;
        }
    }

    // 统计以i开头的第一个系列的斜线
    String []tmpResult = new String[len1 + len2];
    for (i = 0; i < len1; i++) {

        int tmpI = i;
        StringBuilder sb = new StringBuilder();
        for (j = 0; j < len2 && tmpI < len1; j++, tmpI++) {
            int index = tmpI + j * len1;
            sb.append(matrix[index]);
        }
        int tmpResultIndex = i;
        tmpResult[tmpResultIndex] = sb.toString();
    }

    // 统计以j开头的第一个系列的斜线
    for (j = 0; j < len2; j++) {
        int tmpJ = j;
        StringBuilder sb = new StringBuilder();
        for (i = 0; i < len1 && tmpJ < len2; i++, tmpJ ++) {
            int index = i + tmpJ * len1;
            sb.append(matrix[index]);
        }
        //
        int tmpResultIndex = len1 + j;
        tmpResult[tmpResultIndex] = sb.toString();
    }

    // 求最长连续子序列
    for (i = 0; i < tmpResult.length; i++) {
        int tmpMax = 0;
        String tmpString = tmpResult[i];
        for (j = 0; j < tmpString.length(); j++) {
            int value = Integer.parseInt(tmpString.substring(j, j + 1));
            if (value == 1) {
                tmpMax++;
            } else {
                maxLength = Math.max(maxLength, tmpMax);
                tmpMax = 0;
            }
        }
        maxLength = Math.max(maxLength, tmpMax);
    }


    return maxLength;
}