［等待填坑］
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
// // SPOJ LCS.cpp // playground // // Created by Adam Chang on 2015/08/08. // Copyright © 2015年 Adam Chang. All rights reserved. // #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; struct SAM_State{ int mxn; SAM_State *to[26]; SAM_State *parent; SAM_State(int _mxn){ mxn = _mxn; memset(to, 0, sizeof(to)); parent = NULL; } }; SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){ SAM_State *p = last; SAM_State *np = new SAM_State(p -> mxn + 1); while (p && p -> to[ch] == NULL) { p -> to[ch] = np; p = p -> parent; } if (p != NULL) { SAM_State *q = p -> to[ch]; if (q -> mxn == p -> mxn + 1) { np -> parent = q; }else{ SAM_State *nq = new SAM_State(p -> mxn + 1); nq -> parent = q -> parent; q -> parent = nq; np -> parent = nq; memcpy(nq -> to, q -> to, sizeof(q -> to)); while (p && p -> to[ch] == q) { p -> to[ch] = nq; p = p -> parent; } } }else{ np -> parent = root; } last = np; return last; } SAM_State* SAM_Build(string str){ SAM_State *root = new SAM_State(0); SAM_State *last = root; for (int i = 0; i < str.size(); i++) { last = SAM_Append(last, root, str[i] - 'a'); } return root; } int main(){ string a,b; cin >> a >> b; SAM_State *sam_root = SAM_Build(a); SAM_State *sam = sam_root; int ans = 0; int curcnt = 0; for (int i = 0; i < b.size(); i++) { if (sam -> to[b[i]-'a'] != NULL) { curcnt++; sam = sam -> to[b[i]-'a']; }else{ ans = max(curcnt,ans); curcnt = 0; while (sam -> parent) { sam = sam -> parent; if (sam -> to[b[i]-'a'] != NULL) { curcnt = sam->mxn+1; sam = sam -> to[b[i]-'a']; break; } } } } cout << max(curcnt,ans) << endl; return 0; } |
August 19, 2015
为啥没有留言板
August 20, 2015
觉得没啥用的样子。。。