preface

Personal summary: String Learning & summary (mainly the summary template)

1. I haven't painted the topic for a long time. I regret not sticking to it. Now, brush the string & Computational Geometry & DP. For others, such as number theory and graph theory, it's ok to be familiar with that very basic algorithm.
2. Thematic portal: [kuangbin takes you to fly] topic 1-23
3. I feel that directly brushing the question list on cf should help cf score quickly: A list of questions on codeforces (simplified version)

Topic (kmp algorithm should actually be called prefix function algorithm)

1. Number Sequence HDU - 1711 (KMP template question: find the position where a string appears in another string)

1. Portal: Number Sequence HDU - 1711
2. Meaning: String - > number ('#' - > 1E7), and then KMP template (find the position where a string first appears in another string)
3. code:

#include <iostream>
#include <string>
#define dbg(x) cout << #x << "===" << x << endl
using namespace std;
const int N = 2e6 + 10;
int n, m;
int a[N], b[N];

//Online algorithm: that is, it can be input one character at a time
//It is not so much KMP algorithm as prefix function algorithm. KMP is just an application
int pi[N];  //Prefix array

//Get the prefix function, that is, the value of the prefix array
//Note whether s or s+1 enters the function?
//Of course it's s s. I find that I've never written the kmp of s+1 before. (after that, brush more questions and talk about it)
void get(char *s, int l) {
    for (int i = 1; i < l; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
}

//######################Write different things according to different topics:

signed main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < m; i++) cin >> b[i];
        int len = m;
        b[len++] = 1e7;
        for (int i = 0; i < n; i++) b[len++] = a[i];
        //Note that b is found in a
        for (int i = 1; i < len; i++) {
            int j = pi[i - 1];
            while (j > 0 && b[i] != b[j]) j = pi[j - 1];
            if (b[i] == b[j]) j++;
            pi[i] = j;
        }
        // for (int i = 0; i < len; i++) cout << b[i] << " ";
        // cout << endl;
        // for (int i = 0; i < len; i++) cout << pi[i] << " ";
        // cout << endl;
        bool f = false;
        for (int i = 0; i < len; i++) {
            if (pi[i] == m) {
                f = true;
                cout << i - 2 * m + 1 << endl;
                break;
            }
        }
        if (!f) cout << -1 << endl;
    }
    return 0;
}

2. Oulipo HDU - 1686 (KMP template question: find the number of occurrences of one substring in another substring)

1. Oulipo HDU - 1686
2. Find the number of times a substring appears in another substring
3. Problem solving & Code: (omitted) KMP template problem

3. Cut cloth strip HDU - 2087 (KMP template question: find out the maximum number of this string in another string)

1. Cut cloth strip HDU - 2087
2. How many strings can be cut out of another string
3. Problem solution: kmp template problem, omitted
4. Code: omitted

4. Cyclic nackle HDU - 3746 (prefix function template question: find string period n-pi[n-1])

1. Cyclic Nacklace HDU - 3746
2. Question meaning: find the string period
3. Solution: n-pi[n-1]
4. Code: omitted, but pay attention
   1. C + + is wa, G + + is ac
   2. CIN > > on TLE, scanf on tle (the number of CIN > > 1E7 may be a little uncomfortable. I don't know if it's time to wait for tle to use scanf in the official competition. Habit problem emmm)

5. Period HDU - 1358 (prefix function template question: find the period i+1-pi[i]) of string prefix)

1. Period HDU - 1358
2. Meaning & Solution & Code: omitted

6. The Minimum Length HUST - 1010

1. The Minimum Length HUST - 1010

7. Power Strings POJ - 2406 (find periodic water question + 1, omitted)

1. Power Strings POJ - 2406

8. Seek the Name, Seek the Fame POJ - 2752

1. Seek the Name, Seek the Fame POJ - 2752
2. Meaning: print all prefix substring positions of both prefix and suffix
   1. The substring position is the starting position, and pay attention to the position when printing. We start with 1 by pressing the subscript
3. Solution:
   1. When finding the prefix function, press the subscript to start from 0
   2. This problem involves the algorithm principle of finding prefix function
4. code:

#include <cstring>
#include <iostream>
#include <set>
#include <string>
#define dbg(x) cout << #x << "===" << x << endl
using namespace std;
const int N = 4e5 + 10;
char s[N];
int n;
//Online algorithm: that is, it can be input one character at a time
//It is not so much KMP algorithm as prefix function algorithm. KMP is just an application
int pi[N];  //Prefix array

//Get the prefix function, that is, the value of the prefix array
//Note whether s or s+1 enters the function?
//Of course it's s s. I find that I've never written the kmp of s+1 before. (after that, brush more questions and talk about it)
void get(char *s, int l) {
    for (int i = 1; i < l; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
}

//######################Write different things according to different topics:
void dfs(int p) {
    if (!p) return;
    dfs(pi[p - 1]);
    printf("%d ", p);
}
signed main() {
    while (scanf("%s", s) != EOF) {
        n = strlen(s);
        get(s, n);
        dfs(n);  //The traversal order is from large to small, and the printing order is from small to large
        puts("");
    }
    return 0;
}

9. Blue Jeans POJ - 3080 (violent water problem: find the longest common substring of no more than 10 strings with length of 60)

1. Blue Jeans POJ - 3080
2. Question meaning: find the longest common substring of no more than 10 strings with a length of 60. Only substrings with a length greater than or equal to 3 are required (if "no significant commonalities" is not output). If the lengths are equal, the string with the smallest dictionary order is output.
3. Solution: maybe xxx algorithm can be used, but can violence or violence emm
4. code:

#include <iostream>
#include <string>
#define dbg(x) cout << #x << "===" << x << endl;
using namespace std;
const int N = 15;
string s[N];
int n;
signed main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> s[i];
        string ans, str;
        // dbg(ans.size());
        // dbg(str.size());
        bool f;
        for (int len = 3; len <= 60; len++) {
            // dbg(len);
            for (int i = 0; i + len - 1 < 60; i++) {
                str = s[1].substr(i, len);  //Enumeration string
                // dbg(str);
                f = true;

                for (int j = 2; j <= n; j++) {
                    bool f1 = false;
                    for (int ii = 0; ii + len - 1 < 60; ii++) {
                        if (s[j].substr(ii, len) == str) {
                            f1 = true;
                            break;
                        }
                    }
                    if (!f1) {
                        f = false;
                        break;
                    }
                }
                if (f) {
                    // dbg(str);
                    if (ans.size() < len)
                        ans = str;
                    else
                        ans = min(ans, str);
                }
            }
        }
        if (ans.size() < 3)
            puts("no significant commonalities");
        else
            cout << ans << endl;
    }
    return 0;
}
/*
3
2
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
3
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
3
CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
*/

10. Simpsons' Hidden Talents HDU - 2594 (kmp water question: omitted)

1. Simpsons' Hidden Talents HDU - 2594

11. Count the string HDU - 3336()

1. Count the string HDU - 3336