首页 > 代码库 > 11111

11111

#include <cstdio>#include <cstring>using namespace std;const int maxn =  250000 + 10;int tot;struct Node{    Node * ch[26],*f;    int l;} nd[maxn << 1], *head, *last;inline void add(int x){    Node * p = &nd[++ tot], *t = last;    p->l = last->l + 1; last = p;    for(; t && !t->ch[x] ;t = t->f) t->ch[x] = p;    if(!t)  p->f = head;    else if(t->l + 1 == t->ch[x]->l)    p->f = t->ch[x];    else    {        Node *r = &nd[++ tot], *q = t->ch[x];        *r = *q;    r->l = t->l + 1;  p->f = q->f = r;        for(; t && t->ch[x] == q ;t = t->f) t->ch[x] = r;    }}inline void init(){    head = last = &nd[tot];}inline int scan(char *s){    int n = 1;  for(s[0] = getchar();s[0] < ‘a‘ && s[0] > ‘z‘;s[0] = getchar());    for(s[n] = getchar();s[n] >= ‘a‘ && s[n] <= ‘z‘;s[n] = getchar())   n ++;    return n;}char str[maxn];int main(){    init();    int len = scan(str);    for(int i = 0;i < len;i ++) add(str[i] - ‘a‘);    len = scan(str);    Node *p = head; int ans = 0,t = 0;    for(int i = 0;i < len;i ++,ans = ans < t ? t : ans)    {        int x = str[i] - ‘a‘;        if(p->ch[x]) t ++,p = p->ch[x];        else        {            for(; p && !p->ch[x] ;p = p->f);            if(p)   t = p->l + 1,p = p->ch[x];            else    p = head,t = 0;        }    }    printf("%d\n",ans);    return 0;}/*int debug(){    init();    int len = scan(str);    for(int i = 0;i < len;i ++) add(str[i] - ‘a‘);    while(len = scan(str))    {        Node *p = head; int ok = 1;        for(int i = 0;i < len;i ++)        {            p = p->ch[str[i] - ‘a‘];            if(p == NULL)   { ok = 0;   break; }        }        puts((ok ? "Yes" : "No"));    }    return 0;}*/