跳至正文

USACO 2.3.1 Longest Prefix 解题报告

这个题目我也不知道这算法叫什么,反正就是用f[i]记录第i个字符能否到达,如果可以到达再把所有的元素一个个和i之后的进行比较,如果完全相同那么就把f中那个元素的长度加上i的值标记为1。 其实怎么说呢,就是有一个大的数组记录第i个是否能够有那些元素组成,如果可以就从这里再和所有的元素比较下,如果有相匹配的话就产生了一个更长的前缀,把它标记,然后再进行循环。 如果还是没有懂的话,那就看代码吧: / LANG: C ID: yylogoo1 PROG: prefix / #include #include char sub[200][11]; int count; char str[200001]; int len; int f[200001]; int main(void) { int i, j, k; int ans; freopen("prefix.in", "r", stdin); freopen("prefix.out", "w", stdout); while(scanf("%s", sub[count]) && sub[count][0] != '.'){ count++; } while(scanf("%s", &str[len]) == 1){ len += strlen(&str[len]); } f[0] = 1; / Misatck 1: 当答案是len时就会出问题 for(i = 0; i 20001的时候就可能会溢出了. for(k = 0; sub[j][k] != '\0'; k++){ / for(k = 0; sub[j][k] != '\0' && (i + k)

发表回复

您的电子邮箱地址不会被公开。