POJ 1580 String Matching 模拟，简单DP

思路没什么好说的。简单DP。
囧~开始果断又是想复杂了。折腾好久都没出来。。。原来就三个for。。。晕~
说起来是真没意识到这是动规呢。

164K  0MS   C++   716B

#include"cstdio"
#include"cstring"
char s1[200],s2[200];
int gcd(int a,int b)
{
return b ? gcd(b,a % b) : a;
}
int main()
{
while(scanf("%s",s1) && s1[0] != '-'){
scanf("%s",s2);
if(!strcmp(s1,s2)){printf("appx(%s,%s) = 1\n",s1,s2);continue;}
int max = 0,t = 0;
int len1 = strlen(s1),len2 = strlen(s2);
for(int i = 0;i < len1;i ++){
for(int j = 0;j < len2;j ++){
for(int i1 = i,j1 = j;i1 < len1 && j1 < len2;i1 ++,j1 ++)
if(s1[i1] == s2 [j1])t ++;
if(t > max)max = t;
t = 0;
}
}
if(!max){printf("appx(%s,%s) = 0\n",s1,s2);continue;}
int x = max * 2,y = len1 + len2;
printf("appx(%s,%s) = %d/%d\n",s1,s2,x / gcd(x,y),y / gcd(x,y));
}
return 0;
}