HDU 5510 Bazinga（KMP||strstr神器+些许优化）

末蓝、 2022-06-08 13:18 115阅读 0赞

Ladies and gentlemen, please sit up straight.  
**Don't tilt your head**. I'm serious.  
![ef744836a56868c6bc6cc87863ee3092_v_1506297551][]  
For n n given strings S1,S2,⋯,Sn S1,S2,⋯,Sn, labelled from 1 1 to n n, you should find the largest i(1≤i≤n) i (1≤i≤n) such that there exists an integer j(1≤j<i) j (1≤j<i) and Sj Sj is not a substring of Si Si.  
  
A substring of a string Si Si is another string that occurs **in** Si Si. For example, \`\`ruiz" is a substring of \`\`ruizhang", and \`\`rzhang" is not a substring of \`\`ruizhang".

Input

The first line contains an integer t(1≤t≤50) t (1≤t≤50) which is the number of test cases.  
For each test case, the first line is the positive integer n(1≤n≤500) n (1≤n≤500) and in the following n n lines list are the strings S1,S2,⋯,Sn S1,S2,⋯,Sn.  
All strings are given in lower-case letters and strings are no longer than 2000 2000letters.

Output

For each test case, output the largest label you get. If it does not exist, output −1 −1.

Sample Input

4
    5
    ab
    abc
    zabc
    abcd
    zabcd
    4
    you
    lovinyou
    aboutlovinyou
    allaboutlovinyou
    5
    de
    def
    abcd
    abcde
    abcdef
    3
    a
    ba
    ccc

Sample Output

Case #1: 4
    Case #2: -1
    Case #3: 4
    Case #4: 3

题解：

题意：

让你从一堆有编号的串中找出最后面的一个i，使得在\[1，i-1\]中可以找到一个串s\[j\]不是s\[i\]的子串

思路：

直接搞看上去都是要炸的，所以要做一些优化，比如如果s\[j-1\]是s\[j\]的子串，那么如果s\[j-1\]不是s\[i\]的子串，那么s\[j\]也不是，反之如果s\[j\]是s\[i\]的子串，那么s\[j-1\]也一定是s\[i\]的子串，这样想预处理扫一遍数组，将前后有这种包含关系的标记一下就好了，然后从后面往前暴力扫

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    #define ll long long
    #define INF 1008611111
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    using namespace std;
    char s[505][2005];
    int vis[505];
    int main()
    {
        int i,j,k,test,q,n,d;
        scanf("%d",&test);
        for(q=1;q<=test;q++)
        {
            scanf("%d",&n);
            for(i=1;i<=n;i++)
            {
                scanf("%s",s[i]);
                vis[i]=0;
            }
            printf("Case #%d: ",q);
            d=-1;
            for(i=2;i<=n;i++)
            {
                if(strstr(s[i],s[i-1])!=NULL)
                    vis[i-1]=1;
            }
            for(i=n;i>=1;i--)
            {
                for(j=1;j<i;j++)
                {
                    if(vis[j])
                        continue;
                    if(strstr(s[i],s[j])==NULL)
                    {
                        d=i;
                        goto loop;
                    }
                }
            }
            loop:;
            printf("%d\n",d);
        }
        return 0;
    }

[ef744836a56868c6bc6cc87863ee3092_v_1506297551]: https://odzkskevi.qnssl.com/ef744836a56868c6bc6cc87863ee3092?v=1506297551