SPOJ 1811. Longest Common Substring(LCS, 최대 공통 문자열 2개, 접미사 로봇 SAM)
17441 단어 substring
A string is finite sequence of characters over a non-empty finite set Σ.
In this problem, Σ is the set of lowercase letters.
Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.
Now your task is simple, for two given strings, find the length of the longest common substring of them.
Here common substring means a substring of two or more strings.
Input
The input contains exactly two lines, each line consists of no more than 250000 lowercase letters, representing a string.
Output
The length of the longest common substring. If such string doesn't exist, print "0"instead.
Example
Input:
alsdfkjfjkdsal
fdjskalajfkdsla
Output:
3
접미사 로봇 SAM의 템플릿 문제입니다.
다시 SAM.
1 /* ***********************************************
2 Author :kuangbin
3 Created Time :2013-9-8 23:27:46
4 File Name :F:\2013ACM \ \
ew\SPOJ_LCS.cpp
5 ************************************************ */
6
7 #include <stdio.h>
8 #include <string.h>
9 #include <iostream>
10 #include <algorithm>
11 #include <vector>
12 #include <queue>
13 #include <set>
14 #include <map>
15 #include <string>
16 #include <math.h>
17 #include <stdlib.h>
18 #include <time.h>
19 using namespace std;
20
21 const int CHAR = 26;
22 const int MAXN = 250010;
23 struct SAM_Node
24 {
25 SAM_Node *fa, *next[CHAR];
26 int len;
27 int id, pos;
28 SAM_Node(){}
29 SAM_Node(int _len)
30 {
31 fa = 0;
32 len = _len;
33 memset(next,0,sizeof(next));
34 }
35 };
36 SAM_Node SAM_node[MAXN*2], *SAM_root, *SAM_last;
37 int SAM_size;
38 SAM_Node *newSAM_Node(int len)
39 {
40 SAM_node[SAM_size] = SAM_Node(len);
41 SAM_node[SAM_size].id = SAM_size;
42 return &SAM_node[SAM_size++];
43 }
44 SAM_Node *newSAM_Node(SAM_Node *p)
45 {
46 SAM_node[SAM_size] = *p;
47 SAM_node[SAM_size].id = SAM_size;
48 return &SAM_node[SAM_size++];
49 }
50 void SAM_init()
51 {
52 SAM_size = 0;
53 SAM_root = SAM_last = newSAM_Node(0);
54 SAM_node[0].pos = 0;
55 }
56 void SAM_add(int x,int len)
57 {
58 SAM_Node *p = SAM_last, *np = newSAM_Node(p->len + 1);
59 np->pos = len;
60 SAM_last = np;
61 for(; p && !p->next[x];p = p->fa)
62 p->next[x] = np;
63 if(!p)
64 {
65 np->fa = SAM_root;
66 return;
67 }
68 SAM_Node *q = p->next[x];
69 if(q->len == p->len + 1)
70 {
71 np->fa = q;
72 return;
73 }
74 SAM_Node *nq = newSAM_Node(q);
75 nq->len = p->len + 1;
76 q->fa = nq;
77 np->fa = nq;
78 for(; p && p->next[x] == q; p = p->fa)
79 p->next[x] = nq;
80 }
81 void SAM_build(char *s)
82 {
83 SAM_init();
84 int len = strlen(s);
85 for(int i = 0;i < len;i++)
86 SAM_add(s[i] - 'a', i+1);
87 }
88 char str1[MAXN], str2[MAXN];
89 int main()
90 {
91 //freopen("in.txt","r",stdin);
92 //freopen("out.txt","w",stdout);
93 while(scanf("%s%s",str1,str2) == 2)
94 {
95 SAM_build(str1);
96 int len = strlen(str2);
97 SAM_Node *tmp = SAM_root;
98 int ans = 0;
99 int t = 0;
100 for(int i = 0;i < len;i++)
101 {
102 if(tmp->next[str2[i]-'a'])
103 {
104 tmp = tmp->next[str2[i]-'a'];
105 t++;
106 }
107 else
108 {
109 while(tmp && !tmp->next[str2[i]-'a'])
110 tmp = tmp->fa;
111 if(tmp == NULL)
112 {
113 tmp = SAM_root;
114 t = 0;
115 }
116 else
117 {
118 t = tmp->len + 1;
119 tmp = tmp->next[str2[i]-'a'];
120 }
121 }
122 ans = max(ans,t);
123 }
124 printf("%d
",ans);
125 }
126 return 0;
127 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
가장 많이 나타나는 오류 - 1주차예를 들면 다음 코드를 실행하면 바로 이 오류가 뜬다. 오류 발생 이유: iterable 객체 자리에 정수형 자료(int)를 입력했기 때문. C++처럼 10을 넣으면 10번을 반복해준다는게 아니다. iterable ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.