首页 > > 程序设计 > C/C++ >

HDU 5510---Bazinga（指针模拟）

2018-06-17 23:43:04来源：未知阅读 ()

题目链接

http://acm.hdu.edu.cn/search.php?action=listproblem

Problem Description

Ladies and gentlemen, please sit up straight.
Don't tilt your head. I'm serious.

For

Input

The first line contains an integer

Output

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

Sample Input

abc

zabc

abcd

zabcd

you

lovinyou

aboutlovinyou

allaboutlovinyou

def

abcd

abcde

abcdef

ccc

Sample Output

Case #1: 4

Case #2: -1

Case #3: 4

Case #4: 3

Source

2015ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）

Recommend

wange2014 | We have carefully selected several similar problems for you: 5910 5909 5908 5907 5906

题意：输入n 然后输入n个字符串，求最大的i 要求1~i-1中有一个串不是i的子串？

思路：分析复杂度可知这n个字符串比较次数只能是O（n）那么发现可以用指针模拟的办法解决。具体做法：定义l和r 如果l是r的子串，那么l++ 继续判断l是否是r的子串，否则ans=r，为什么这样呢？如果l是r的子串那么l++ 由它可知1~l-1 这些串一定是l~r这些串中一些串的子串，那么1~l-1这些串不必再和r后面的串进行比较；

代码如下：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <queue>

using namespace std;
typedef long long LL;
char s[600][2005];
int nex[2005];

void makeNext(char p[])
{
    int q,k;
    int m=strlen(p);
    nex[0]=0;
    for(q=1,k=0; q<m; ++q)
    {
        while(k>0&&p[q]!=p[k])
            k=nex[k-1];
        if(p[q]==p[k]) k++;
        nex[q]=k;
    }
}
int calc(int x,int y)
{
    makeNext(s[x]);
    int l=strlen(s[x]);
    int len=strlen(s[y]);
    int q,k;
    for(q=0,k=0; q<len; q++)
    {
        while(k>0&&s[y][q]!=s[x][k])
            k=nex[k-1];
        if(s[y][q]==s[x][k]) k++;
        if(k>=l) return 1;
    }
    return 0;
}

int main()
{
    int T,Case=1;
    cin>>T;
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
            scanf("%s",s[i]);
        int l = 1, r = 2, ans = -1;
        while(r <= n)
        {
            while(l < r)
            {
                if(calc(l,r))  l++;
                else { ans=r; break; }
            }
            r++;
        }
        printf("Case #%d: %d\n",Case++,ans);
    }
    return 0;
}