최 장 공통 문자열 Longest common subString

가장 긴 공통 문자열 (Longest Common subString) 을 두 문자열 로 간소화 하 는 경 우 는 두 문자열 A, B 가 같은 하위 문자열 중 가장 긴 하 나 를 찾 아 연속 을 요구 하 는 것 이다.이것 은 가장 긴 공공 하위 서열 과 달리 가장 긴 공공 하위 서열 은 연속 되 지 않 을 수 있다.
알고리즘:
두 문자열 의 가장 긴 공공 문자열 을 찾 습 니 다. 이 문자열 은 원래 문자열 에서 연속 되 어야 합 니 다.사실은 이것 은 또 하나의 일관성 있 는 결정 문제 로 동태 적 인 계획 으로 해결 할 수 있다.우 리 는 2 차원 행렬 을 채택 하여 중간의 결 과 를 기록한다.이 2 차원 행렬 은 어떻게 구성 합 니까?직접 예 를 들 어 'bab' 와 'caba' (물론 우 리 는 지금 한눈 에 가장 긴 공공 문자열 이 'ba' 또는 'ab' 인 것 을 알 수 있다) b a b c 0 0 a 0 0 0 b 1 0 1 a 0 0 1 a 0 1 0 1 a 0 1 0 을 보면 행렬 의 경사 대각선 이 가장 긴 것 을 보면 가장 긴 공공 문자열 을 찾 을 수 있다.그러나 2 차원 매트릭스 에서 가장 긴 1 로 구 성 된 사각 선 을 찾 는 것 도 번 거 로 운 일이 다. 다음 개선 은 매트릭스 가 1 을 채 울 때 왼쪽 상단 원소 에 1 을 더 하 는 것 과 같다.b a b c 0 0 a 0 0 b 1 0 2 a 0 20 과 같은 행렬 의 가장 큰 요 소 는 가장 긴 공공 문자열 의 길이 이다.알고리즘 도 개선 할 수 있 습 니 다. 우 리 는 최대 길이 와 대응 하 는 문 자 를 찾 는 작업 을 행렬 을 구성 하 는 과정 에서 완성 할 수 있 습 니 다. 구 조 를 하면 서 현재 의 최대 길이 와 대응 하 는 위 치 를 기록 하면 n ^ 2 의 검색 시간 을 절약 할 수 있 습 니 다.공간 적 으로 도 개선 할 수 있 습 니 다. 만약 에 상기 방식 으로 구 조 를 하면 행렬 의 i + 1 줄 의 값 계산 이 완 료 된 후에 i 줄 의 값 은 소 용이 없습니다. 가장 긴 길이 가 i 줄 에 나타 나 더 라 도 우 리 는 변수 로 기록 되 었 습 니 다.따라서 행렬 을 하나의 벡터 로 줄 여 처리 할 수 있 습 니 다. 벡터 의 현재 값 은 i 줄 에 대응 하고 벡터 의 다음 순환 후의 값 은 i + 1 줄 에 대응 합 니 다.
주의: 내부 순환 은 뒤에서 앞으로 갑 니 다. c [j] 는 지난번 c [j - 1] 에 의존 하기 때 문 입 니 다.
기교: c 의 길 이 는 내부 순환 길이 보다 1 크 고 c [0] = 0 을 설정 하여 메모리 순환 문자 0 의 위 치 를 판단 하 는 특수 처 리 를 피한다.
Code：

////	      （  ）	LCS
//     ，           。
//Sample Input：
//SULAODASHANGBINGHAIHAIGAN BINGHAIZHANGFESUDAFVGTPWH
//Sample Output：
//BINGHAI
//          ，           
#include <iostream>
#include <cstring>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=1000;
int LCStr(char *str1,int len1,char *str2,int len2,char **lcstr){
	int i,j;
	int *c=new int[len2+1];
	int maxcount=0,maxindex=0;
	memset(c,0,sizeof(int)*len2);
	for(i=0;i<len1;i++){
		for(j=len2;j>0;j--){//current count from len2 to 1;
			if(str1[i]==str2[j-1]){
				c[j]=c[j-1]+1;
				if(c[j]>=maxcount){
					maxcount=c[j];
					maxindex=j-1;//the current index of str2 is j-1;
				}
			}else
				c[j]=0;
		}
	}
	if(maxcount==0)
		return 0;
	*lcstr=new char[maxcount+1];
	for(i=0;i<maxcount;i++)
		(*lcstr)[i]=str2[maxindex-maxcount+1+i];
	(*lcstr)[i]='\0';
	return maxcount;
}

int main()
{
	char str1[N];
	char str2[N];
	while(scanf("%s%s",&str1,&str2)!=EOF){
		int len1 = strlen(str1);
		int len2 = strlen(str2);
		char *lcs=NULL;
		int len = LCStr(str1 , len1 , str2 , len2 , &lcs);
		for(int i = 0 ; i < len ; ++i)
			printf("%c",lcs[i]);
		printf("
");
	}
}

참고:
화하 35 도, 하위 꼬치 의 몇 가지 상황 을 정리 했다.http://www.cnblogs.com/zhangchaoyang/articles/2012070.html
비교적 좋 은 범례:http://blog.csdn.net/steven30832/article/details/8260189