HDU 5510

ゝ一世哀愁。 2023-08-17 16:37 77阅读 0赞

题意略。

思路：

这算是个铜牌题吧。思路是kmp+栈（类似于单调栈的那种想法），每个字符串进栈说明当前的栈是空栈，或者说该字符串在与栈顶元素比较时，

碰到了之前的不是它字串的字符串。

我们从前往后遍历这些字符串，

如果栈顶字符串是它的字串，那么我就弹出栈顶元素，继续比较。

如果栈顶字符串不是它的字符串，那么我就将当前字符串压入栈，并记录当前字符串标号。

有几个优化：

1.预先把字符串长度计算出来，如果栈顶字符串比当前字符串长，那么我们可以肯定，栈顶字符串不是当前字符串的字串。

2.预先把所有字符串的kmpNext数组处理好。

每个字符串进栈一次，出栈一次，总复杂度200 \* 500 \* 2。

代码附上：

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int maxn0 = 505;
     4 const int maxn1 = 2005;
     5 
     6 int len[maxn0],stk[maxn0],kmpNext[maxn0][maxn1],t,n,tp;
     7 char str[maxn0][maxn1];
     8 
     9 void preKMP(char mode[],int m){
    10     int i = 0,j = kmpNext[m][0] = -1;
    11     while(mode[i]){
    12         while(j != -1 && mode[j] != mode[i]) j = kmpNext[m][j];
    13         if(mode[++j] == mode[++i]) kmpNext[m][i] = kmpNext[m][j];
    14         else kmpNext[m][i] = j;
    15     }
    16 }
    17 int kmp(char mode[],char str[],int m){
    18     int ret = 0;
    19     int i = 0,j = 0;
    20     while(str[i]){
    21         while(j != -1 && mode[j] != str[i]) j = kmpNext[m][j];
    22         ++i;++j;
    23         if(!mode[j]){
    24             ++ret;
    25             break;
    26         }
    27     }
    28     return ret;
    29 }
    30 
    31 int main(){
    32     scanf("%d",&t);
    33     int cas = 1;
    34     while(t--){
    35         tp = 0;
    36         scanf("%d",&n);
    37         for(int i = 0;i < n;++i){
    38             scanf("%s",str[i]);
    39             preKMP(str[i],i);
    40             len[i] = strlen(str[i]);
    41         }
    42         
    43         int lastest = -1;
    44         stk[tp++] = 0;
    45         for(int i = 1;i < n;++i){
    46             if(len[tp - 1] > len[i]){
    47                 stk[tp++] = i;
    48                 lastest = i;
    49                 continue;
    50             }
    51             
    52             while(tp > 0 && kmp(str[stk[tp - 1]],str[i],stk[tp - 1]) > 0) --tp;
    53             if(tp > 0) lastest = i;
    54             stk[tp++] = i;
    55         }
    56         printf("Case #%d: %d\n",cas++,lastest == -1 ? -1 : lastest + 1);
    57     }
    58     return 0;
    59 }

转载于:https://www.cnblogs.com/tiberius/p/11455752.html