最大公共子串

最大公共子串

题目描述

从一个给定的串中删去（不一定连续地删去）0个或0个以上的字符，剩下地字符按原来顺序组成的串。例如：“ ”，“a”，“xb”，“aaa”，“bbb”，“xabb”，“xaaabbb”都是串“xaaabbb”的子串。（例子中的串不包含引号。）   编程求N个非空串的最长公共子串的长度。限制：2<=N<=100；N个串中的字符只会是数字0，1，…，9或小写英文字母a，b，…，z；每个串非空且最多含100个字符；N个串的长度的乘积不会超过30000。

输入

文件第1行是一个整数T，表示测试数据的个数（1<=T<=10）。接下来有T组测试数据。各组测试数据的第1行是一个整数Ni，表示第i组数据中串的个数。各组测试数据的第2到N+1行中，每行一个串，串中不会有空格，但行首和行末可能有空格，这些空格当然不算作串的一部分。

输出

输出T行，每行一个数，第i行的数表示第i组测试数据中Ni个非空串的最长公共子串的长度。

示例输入

1 3 ab bc cd

示例输出

0 题意：求n个字符串的最长公共子串。 以下是在百度贴吧找到的解题思路： AC代码： [cpp] view plain copy #include <cstring>  #include <string>  #include <cstdio>  #include <algorithm>  #include <queue>  #include <cmath>  #include <vector>  #include <cstdlib>  #include <iostream>  #define max2(a,b) ((a) > (b) ? (a) : (b))  #define min2(a,b) ((a) < (b) ? (a) : (b))    using namespace std;    char s[105][105];  int len[105];  int dp[30005];  int n;  int LCS(int *x)  {      int index,i,j,ret;      //如果当前有字符串的长度为0，则返回0      for(i=1;i<=n;i++)      if(x[i]==0) return 0;      //建立映射      for(index=x[n]-1,i=n-1;i>=1;i--)      index=index*len[i]+x[i]-1;      //记忆化搜索      if(dp[index]>=0) return dp[index];      //判断是否所有串的最后一个字符都相等      for(i=2;i<=n;i++)      if(s[1][x[1]-1]!=s[i][x[i]-1])      break;      if(i>n)    //如果都相等，则最大长度+1      {          for(j=1;j<=n;j++)          x[j]--;          ret=LCS(x)+1;          for(j=1;j<=n;j++)          x[j]++;      }      else      //否则，求删去某个字符串的最后一个字符之后得到的最大值      {          ret=0;          for(j=1;j<=n;j++)          {              x[j]--;              int t=LCS(x);              ret=max2(t,ret);              x[j]++;          }      }      dp[index]=ret;      return ret;  }  int main()  {      int t;      int temp[105];      scanf("%d",&t);      while(t--)      {          scanf("%d",&n);          for(int i=1;i<=n;i++)          {              scanf("%s",s[i]);              len[i]=temp[i]=strlen(s[i]);          }          memset(dp,-1,sizeof(dp));          printf("%d\n",LCS(temp));      }      return 0;  }