本文共 1804 字，大约阅读时间需要 6 分钟。
t题目链接：
题目：
题意：找到一个编号最大的字符串满足：存在一个编号比它小的字符串不是它的字串。
思路：KMP。但是这题的复杂度极大，杭电服务器跑稳T，我还试了一发-_-||。想了很久想到一个玄学优化，我们首先比较相邻的两个字符串，假设为i和i-1，且i-1是i的字串，那么如果某个大编号包含i则必然包含i-1，此时就没有必要再和i-1跑一边KMP了。如下图所示：
代码实现如下：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 using namespace std;15 16 typedef long long ll;17 typedef pair pll;18 typedef pair pli;19 typedef pair pil;;20 typedef pair pii;21 typedef unsigned long long ull;22 23 #define lson i<<124 #define rson i<<1|125 #define bug printf("*********\n");26 #define FIN freopen("D://code//in.txt", "r", stdin);27 #define debug(x) cout<<"["< <<"]" < 0 && s[x][i] != s[x][j+1]) j = nex[x][j];45 if(s[x][i] == s[x][j+1]) j++;46 nex[x][i] = j;47 }48 }49 50 bool kmp(int x, int y) {51 for(int i = 1, j = 0; i <= len[x]; i++) {52 while(j > 0 && (j == len[y] || s[x][i] != s[y][j+1])) j = nex[y][j];53 if(s[x][i] == s[y][j+1]) j++;54 if(j == len[y]) {55 return true;56 }57 }58 return false;59 }60 61 int main() {62 //FIN;63 scanf("%d", &t);64 int icase = 0;65 while(t--) {66 scanf("%d", &n);67 memset(vis, 0, sizeof(vis));68 for(int i = 1; i <= n; i++) {69 scanf("%s", s[i] + 1);70 len[i] = strlen(s[i] + 1);71 get_next(i);72 }73 int flag = 1;74 for(int i = n; i >= 2; i--) {75 if(kmp(i, i-1)) {76 vis[i-1] = 1;77 }78 }79 for(int i = n; i >= 2; i--) {80 for(int j = i - 1; j >= 1; j--) {81 if(!vis[j] && !kmp(i, j)) {82 flag = i;83 break;84 }85 }86 if(flag != 1) break;87 }88 printf("Case #%d: ", ++icase);89 if(flag != 1) printf("%d\n", flag);90 else printf("-1\n");91 }92 return 0;93 }
转载于:https://www.cnblogs.com/Dillonh/p/9424527.html
