首页 > 代码库 > 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;}*/
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。