SPOJ 1811. Longest Common Substring(LCS, 최대 공통 문자열 2개, 접미사 로봇 SAM)

17441 단어 substring
1811. Longest Common Substring Problem code: LCS
 
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 }

 
 
 
 
 
 
 

좋은 웹페이지 즐겨찾기