Recently, Flymouse reads a book about Algorithm and Data Structure. The book reads: there are two types of LCS Problems. One is
Longest Common Subsequence problem. By the way of Dynamic Programming, we could solve this problem. The other is Longest Common Substring problem, which is to find the longest string that is substrings of the two strings. For example, given the following two strings: 1. flymouseEnglishpoor 2. comeonflymouseinenglish The longest common substring is flymouse, the length of this string is 8.
The first line contains a single integer t (1 <= t <= 100), the number of test cases.There will be two lines for each test case, each line
contains a string (The length of the two strings are no more than 2000 and you can assure all strings will not contains any punctuation or other separators).
For each test case, you should output one line containing the longest common substring?s length of the two strings of the test case.
最长公共子串问题，暴力解决
#include<stdio.h> #include<string.h> char s1[2016],s2[2016]; int len1,len2; int main(){ int t,i,j,k,ans; scanf("%d",&t); while(t--){ ans=0; scanf("%s %s",&s1,&s2); len1=strlen(s1);len2=strlen(s2); for(i=0;i<len1;i++){ if(len1-i<=ans) break; for(j=0;j<len2;j++){ if(s1[i]==s2[j]){ k=1; while(s1[i+k]!='\0'&&s2[j+k]!='\0'&&s1[i+k]==s2[j+k]) k++; if(ans<k) ans=k; } } } printf("%d\n",ans); } return 0; }