当前位置: 代码迷 >> 综合 >> 最大公共子串 oj
  详细解决方案

最大公共子串 oj

热度:0   发布时间:2024-01-14 22:36:35.0

最大公共子串

Time Limit: 1000 ms  Memory Limit: 32768 KiB
Submit  Statistic
Problem Description
从一个给定的串中删去(不一定连续地删去)0个或0个以上的字符,剩下地字符按原来顺序组成的串。例如:“ ”,“a”,“xb”,“aaa”,“bbb”,“xabb”,“xaaabbb”都是串“xaaabbb”的子串。(例子中的串不包含引号。)
 
编程求N个非空串的最长公共子串的长度。限制:2<=N<=100;N个串中的字符只会是数字0,1,…,9或小写英文字母a,b,…,z;每个串非空且最多含100个字符;N个串的长度的乘积不会超过30000。
Input
文件第1行是一个整数T,表示测试数据的个数(1<=T<=10)。接下来有T组测试数据。各组测试数据的第1行是一个整数Ni,表示第i组数据中串的个数。各组测试数据的第2到N+1行中,每行一个串,串中不会有空格,但行首和行末可能有空格,这些空格当然不算作串的一部分。
Output
输出T行,每行一个数,第i行的数表示第i组测试数据中Ni个非空串的最长公共子串的长度。
Sample Input
1
3
ab
bc
cd
Sample Output
0
Hint
Source
#include<stdio.h>  
#include<string.h>  
int dp[33000],Ni,T;  
char inp[101],len[101],a[101][101];  
int getd(int i,int k)  
{  if(i>Ni)return 0;  return getd(i+1,k*len[i])+k*inp[i];  
}  
int sfp()  
{  int p,i,j;  p = getd(0,1);  if(!dp[p])  {  for(i=1;i<=Ni-1;++i)  {  if(a[i][inp[i]]!=a[i+1][inp[i+1]])  break;  }  if(i>Ni-1)  {  for(i=1;i<=Ni;++i)  if(inp[i])  --inp[i];  else  break;  if(i>Ni)  {  j = sfp()+1;  if(j>=dp[p])  dp[p]=j+1;  }  else dp[p]=2;  while((--i)>0)  ++inp[i];  }  else  {  for(i=1;i<=Ni;++i)  {  if(inp[i])  {  --inp[i];  j = sfp();  if(j>=dp[p])  dp[p]=j+1;  ++inp[i];  }  }  if(!dp[p])  dp[p]=1;  }  }  return dp[p]-1;  
}  
int main()  
{  int i,T;  scanf("%d",&T);  while(T)  {  scanf("%d",&Ni);  memset(dp,0,30000*sizeof(int));  len[0]=1;  for(i=1;i<=Ni;++i)  {  scanf("%s",a[i]);  len[i]=strlen(a[i]);  inp[i]=len[i]-1;  }  printf("%u\n",sfp());  --T;  }  return 0;  
}  


  相关解决方案