POJ 2217: Secretary
問題文
http://poj.org/problem?id=2217
Suffix Treeを実装したので最長共通部分文字列の問題にsubmit。
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <cctype> using namespace std; const int SIZE = 128; struct Node { int b,e,d; //begin, end, distance from root Node *parent, *children[128], *suffixLink; Node():b(0),e(0),d(0),parent(NULL),suffixLink(NULL){ fill(children, children + SIZE, (Node *)0); } Node(int b, int e, int d, Node *p):b(b),e(e),d(d),parent(p),suffixLink(NULL){ fill(children, children + SIZE, (Node *)0); } }; int a[30000]; Node *buildSuffixTree(string s){ int n = s.size(); for(int i = 0; i < n; i++)a[i] = (int)s[i]; Node *root = new Node(); Node *node = root; for(int i = 0, tail = 0; i < n; i++, tail++){ Node *last = NULL; while(tail >= 0){ Node *ch = node->children[a[i - tail]]; while(ch != NULL && tail >= ch->e - ch->b){ tail -= ch->e - ch->b; node = ch; ch = ch->children[a[i - tail]]; } if(ch == NULL){ node->children[a[i]] = new Node(i, n, node->d + node->e - node->b, node); if(last != NULL)last->suffixLink = node; last = NULL; } else { int afterTail = a[ch->b + tail]; if(afterTail == a[i]){ if(last != NULL)last->suffixLink = node; break; } else { Node *splitNode = new Node(ch->b, ch->b + tail, node->d + node->e - node->b, node); splitNode->children[a[i]] = new Node(i, n, ch->d + tail, splitNode); splitNode->children[afterTail] = ch; ch->b += tail; ch->d += tail; ch->parent = splitNode; node->children[a[i - tail]] = splitNode; if(last != NULL)last->suffixLink = splitNode; last = splitNode; } } if(node == root)tail--; else node = node->suffixLink; } } return root; } int lcsLength; int lcsBeginIndex; //longest common substring int lcs_traverse(Node *node, int i1, int i2){ if(node->b <= i1 && i1 < node->e)return 1; if(node->b <= i2 && i2 < node->e)return 2; int visited = 0; for(int f = 0; f < SIZE; f++) if(node->children[f] != NULL) visited |= lcs_traverse(node->children[f], i1, i2); if(visited == 3){ int curLength = node->d + node->e - node->b; if(lcsLength < curLength){ lcsLength = curLength; lcsBeginIndex = node->b - node->d; } } return visited; } string lcs(string s1, string s2){ string s = s1 + '\1' + s2 + '\2'; Node *tree = buildSuffixTree(s); lcsLength = 0; lcsBeginIndex = 0; lcs_traverse(tree, s1.size(), s1.size() + s2.size() + 1); return s.substr(lcsBeginIndex, lcsLength); } int main(void){ int n; cin >> n; cin.ignore(); while(n--){ string s1,s2; getline(cin, s1); getline(cin, s2); lcs(s1, s2); cout << "Nejdelsi spolecny retezec ma delku " << lcsLength << "." << endl; } return 0; }