Problem 2128 最长子串

Problem 2128 最长子串

Accept: 55    Submit: 209
Time Limit: 3000 mSec    Memory Limit : 65536 KB

 Problem Description

问题很简单，给你一个字符串s，问s的子串中不包含s1,s2...sn的最长串有多长。

 Input

输入包含多组数据。第一行为字符串s,字符串s的长度1到10^6次方，第二行是字符串s不能包含的子串个数n,n<=1000。接下来n行字符串,长度不大于100。

字符串由小写的英文字符组成。

 Output

最长子串的长度

 Sample Input

lgcstraightlalongahisnstreet 5 str long tree biginteger ellipse

 Sample Output

12

 Source

福州大学第十届程序设计竞赛

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#define maxn 100002
#define LL long long
using namespace std ;

struct node
{
    int x , y ;
}qe[maxn];
char a[maxn] , b[maxn] ;
int len ;
int cmp( node a , node b )
{
    return a.x < b.x ;
}
void find()
{
    int n , m , i , pos = 0 ;
    m = strlen(b) ;
    while(strstr(a+pos,b) != NULL )
    {
        i = strstr(a+pos,b)-a ;
        qe[len].x = i ;
        qe[len].y = i+m-1 ;

        pos = qe[len].y ;
        len++ ;
    }
}
int main()
{
    int i ,k ,j ;
    int n , m , ans ;
  // freopen("in.txt","r",stdin) ;
    while( scanf("%s",a) != EOF )
    {
        len = 0 ;
        cin >> m ;
        while(m--)
        {
            scanf("%s",b) ;
            find() ;
        }
        if(!len)
        {
            cout << strlen(a) << endl;
            continue ;
        }
        sort(qe,qe+len,cmp) ;
        ans = -1 ;
        qe[len].x = qe[len].y = strlen(a) ;
        for( i = 0 ; i < len ;i++ )
        {
           k = qe[i+1].y-qe[i].x-1 ;
           ans = max(k,ans) ;
        }
        cout << ans << endl;
    }
    return 0 ;
}