zoj 3013 Word Segmenting

zoj 3013 Word Segmenting

#include <cstdio>#include <string>#include <cstring>#include <algorithm>#include <queue>#include <cmath>using namespace std;int cntnode;struct Trie{char chr;int son, next, word, suffix, len;bool unsafe;Trie():son(0),word(0),suffix(0),next(0),unsafe(0),len(0) {}} trie[200000];int getchild(int x, char c){int i, p = x;while (1){i = trie[p].son;while (trie[i].chr != c && i != 0)i = trie[i].next;if (trie[i].chr == c && i != 0)return i;else{if (p != 0)p = trie[p].suffix;else return 0;}}}void insert(char* s){int p = 0, k;while (*s){k = trie[p].son;if (k != 0){while (trie[k].chr != *s && trie[k].next != 0)k = trie[k].next;if (trie[k].chr == *s)p = k;else{trie[cntnode] = Trie();trie[cntnode].chr = *s;trie[cntnode].len = trie[p].len + 1;trie[k].next = cntnode;p = cntnode++;}}else{trie[cntnode] = Trie();trie[cntnode].chr = *s;trie[cntnode].len = trie[p].len + 1;trie[p].son = cntnode;p = cntnode++;}s++;}trie[p].word++;trie[p].unsafe = true;}void bfs(){queue<int> q;int p = 0, k, i;i = trie[0].son;while (i != 0){q.push(i);i = trie[i].next;}while (!q.empty()){int fid = q.front();q.pop();i = trie[fid].son;while (i != 0){q.push(i);trie[i].suffix = getchild(trie[fid].suffix, trie[i].chr);if (trie[i].word)trie[i].unsafe = true;elsetrie[i].unsafe = trie[fid].unsafe;i = trie[i].next;}}}void work();int M, N;int f[5000], g[5000], add[5000];char line[10000];int main(){int i, j, k;char wd[100];while (scanf("%d%d", &M, &N) == 2){memset(line, 0, sizeof(line));trie[0] = Trie();cntnode = 1;for (i = 0; i < M; ++i){scanf("%s", wd);insert(wd);}bfs();for (i = 0; i < N; ++i)work();}return 0;}void work(){int p, pp, i, len, segs = 0;string ans;scanf("%s", line + 1);len = strlen(line + 1);memset(f, 127, sizeof(f));memset(g, 0, sizeof(g));memset(add, 0, sizeof(add));p = 0; f[0] = 0;for (i = 1; i <= len; ++i){p = getchild(p, line[i]);pp = p;f[i] = f[i-1] + 1;g[i] = 0;while (pp != 0){if (trie[pp].word && f[i] > f[i-trie[pp].len]){f[i] = f[i-trie[pp].len];g[i] = trie[pp].len;}pp = trie[pp].suffix;}}segs += f[len];p = len;while (p > 0){if (g[p] == 0)--p;else{add[p] = 1;add[p-g[p]] = 1;p -= g[p];}}for (i = 1; i <= len; ++i){ans.append(1, line[i]);if (add[i] && i < len)ans.append(1, '#');}printf("%dn%sn", segs, ans.c_str());}