Problem 3: Threatening Letter [J. Kuipers, 2002]FJ has had a terrible fight with his neighbor and wants to send hima nasty letter, but wants to remain anonymous. As so many beforehim have done, he plans to cut out printed letters and paste themonto a sheet of paper. He has an infinite number of the most recentissue of the Moo York Times that has N (1 <= N <= 50,000) uppercaseletters laid out in a long string (though read in as a series ofshorter strings). Likewise, he has a message he'd like to composethat is a single long string of letters but that is read in as aset of shorter strings.Being lazy, he wants to make the smallest possible number of cuts.FJ has a really great set of scissors that enables him to removeany single-line snippet from the Moo York Times with one cut. Henotices that he can cut entire words or phrases with a single cut,thus reducing his total number of cuts.What is the minimum amount of cuts he has to make to construct hisletter of M (1 <= M <= 50,000) letters?It is guaranteed that it is possible for FJ to complete his task.Consider a 38 letter Moo York Times: THEQUICKBROWNFOXDO GJUMPSOVERTHELAZYDOGfrom which FJ wants to construct a 9 letter message: FOXDOG DOGThese input lines represent a pair of strings: THEQUICKBROWNFOXDOGJUMPSOVERTHELAZYDOG FOXDOGDOGSince "FOXDOG" exists in the newspaper, FJ can cut this piece outand then get the last "DOG" by cutting out either instance of theword "DOG".Thus, he requires but two cuts.PROBLEM NAME: letterINPUT FORMAT:* Line 1: Two space-separated integers: N and M* Lines 2..?: N letters laid out on several input lines; this is the text of the one copy of the Moo York Times. Each line will have no more than 80 characters.* Lines ?..?: M letters that are the text of FJ's letter. Each line will have no more than 80 characters.SAMPLE INPUT (file letter.in):38 9THEQUICKBROWNFOXDOGJUMPSOVERTHELAZYDOGFOXDOGDOGOUTPUT FORMAT:* Line 1: The minimum number of cuts FJ has to make to create his messageSAMPLE OUTPUT (file letter.out):2
一看跟子串相关，就是后缀那一套了。想法是这样的，尽量在文本串中找到更长的子串与当前串匹配。若无法继续匹配了，则重新匹配，答案+1。这里我选择了后缀自动机，实现起来好写。
#include#include const int maxn = 50005;int n, m, ans, now;int sam[maxn << 1][26], len[maxn << 1], link[maxn << 1], sz, last, p, q, cur, clone;char ch;int main(void) { freopen("letter.in", "r", stdin); freopen("letter.out", "w", stdout); scanf("%d%d", &n, &m); link[sz++] = -1; for (int i = 1; i <= n; ++i) { while ((ch = getchar()) < 'A'); cur = sz++; len[cur] = len[last] + 1; for (p = last; p != -1 && !sam[p][ch - 'A']; p = link[p]) { sam[p][ch - 'A'] = cur; } if (p != -1) { q = sam[p][ch - 'A']; if (len[p] + 1 == len[q]) { link[cur] = q; } else { clone = sz++; memcpy(sam[clone], sam[q], sizeof sam[0]); link[clone] = link[q]; len[clone] = len[p] + 1; for (; p != -1 && sam[p][ch - 'A'] == q; p = link[p]) { sam[p][ch - 'A'] = clone; } link[q] = link[cur] = clone; } } last = cur; } for (int i = 1; i <= m; ++i) { while ((ch = getchar()) < 'A'); now = sam[now][ch - 'A']; if (!now) { ++ans; now = sam[0][ch - 'A']; } } if (now) { ++ans; } printf("%d\n", ans); return 0;}
这也算是SAM的模版了叭。