2015沈阳区域赛现场赛第2题
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5510
题意：给定一个由字符串组成的序列，一共n个元素，每个元素是一个不超过2000个字符的字符串。求"存在秩小于 i 且不是 i 的子串"的最大的 i (1<= i <= n)。
数据范围：n [1, 500]，T组输入，T [1, 50]
思路：从1到n-1枚举每个字符串str[i]，判断是否有 j < i 使得str[j]不是str[i]的子串，若有，将 i 标记为当前最优解。枚举结束后最后标记的 i 即为所求；若始终未标记，则不存在，输出-1。
串匹配用了KMP，对同一模式串的next数组只在需要的时候生成一遍，再次需要时直接取用。
另外，开辟一个vis数组记录子串关系以省略一些匹配。即当判断出 str[i] 是 str[j] 的子串时(i < j), 意味着有比 i 秩更大的串 str[j] 包含了 str[i]，那么只匹配str[j]就可以了，对str[i]的匹配是不必要的了，因此标记vis[i]=1以区分。
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 const int MAX_N = 505; 5 const int MAX_L = 2005; 6 7 int T; 8 int n; 9 char str[MAX_N][MAX_L]; 10 int len[MAX_N]; 11 int next[MAX_N][MAX_L]; 12 13 char has_cal[MAX_N];//是否已计算 14 char vis[MAX_N];//是否存在秩更大的母串 15 16 int Index_KMP(int s, int t, int pos, int next[]){ 17 //下标从1开始，[0]无意义 18 int i=pos, j=1; 19 char* S = str[s]; 20 char* T = str[t]; 21 while(i<=len[s] && j<=len[t]){ 22 if(j==0 || S[i]==T[j]){i++; j++;} 23 else j=next[j]; 24 } 25 if(j>len[t]) return i-len[t]; 26 else return 0; 27 } 28 29 void get_next(int t, int* next){ 30 int i=1, j=0; 31 char* T = str[t]; 32 int lt = len[t]; 33 next[0] = next[1] = 0; 34 while(i<lt){ 35 if(j==0 || T[i]==T[j]){next[++i] = ++j;} 36 else j=next[j]; 37 } 38 } 39 40 int main() 41 { 42 freopen("5510.txt", "r", stdin); 43 scanf("%d", &T); 44 for(int ca = 1; ca<=T; ca++){ 45 46 scanf("%d", &n); 47 for(int i=0; i<n; i++){ 48 scanf("%s", str[i]+1); 49 len[i] = 0; 50 for(int j=1; str[i][j]!='\0'; j++){ 51 len[i]++;//统计串长度 52 } 53 } 54 55 memset(vis, 0, sizeof(vis)); 56 memset(has_cal, 0, sizeof(has_cal)); 57 int flag = 0; 58 for(int i=1; i<n; i++){ 59 for(int j=0; j<i; j++){ 60 if(vis[j]) continue; //存在秩比它更大的母串，跳过此次比对 61 if(!has_cal[j]) { 62 get_next(j, next[j]); 63 has_cal[j] = 1; 64 } 65 //printf("%s %s\n", str[i]+1, str[j]+1); 66 if(Index_KMP(i, j, 0, next[j]) == 0){ 67 flag = i+1; 68 break; //i是当前最优解 69 }else vis[j] = 1; 70 } 71 } 72 printf("Case #%d: %d\n", ca, flag ? flag : -1); 73 } 74 return 0; 75 }
