问题 A: 求最长公共子串（串）

题目描述
求采用顺序结构存储的串s和串t的一个最长公共子串，若没有则输出false，若最长的有多个则输出最先出现的那一串。

输入
输入两个字符串

输出
输出公共子串

样例输入

abcdef
adbcef
1
2

样例输出

bc
1

思路：字符串hash。

#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
const LL MOD = 1000000007;
const LL P = 10000019;
const LL MAXN = 1010;
// powP[i]存放P^i%MOD，H1和H2分别存放str1和str2的hash值
LL powP[MAXN], H1[MAXN] = {0}, H2[MAXN] = {0};
struct Node {
    int hashValue, length, start, end;
    Node(int a, int b, int c) :
        hashValue(a), length(b), start(c){};
};
// pr1存放str1的所有<子串hash值,子串长度,子串起始位置>，pr2同理
vector<Node> pr1, pr2;

// init的函数初始化powP函数
void init(int len) {
    powP[0] = 1;
    for (int i = 1; i <= len; i++) {
        powP[i] = (powP[i - 1] * P) % MOD;
    }
}
// calH函数计算字符串str的hash值
void calH(LL H[], string &str) {
    H[0] = str[0]; // H[0]单独处理
    for (int i = 1; i < str.length(); i++) {
        H[i] = (H[i - 1] * P + str[i]) % MOD;
    }
}
// calSingleSubH计算H[i…j]
int calSingleSubH(LL H[], int i, int j) {
    if (i == 0) return H[j]; // H[0…j]单独处理
    return ((H[j] - H[i - 1] * powP[j - i + 1]) % MOD + MOD) % MOD;
}
// calSubH计算所有子串的hash值，并将<子串hash值,子串长度,子串起始位置>存入pr
void calSubH(LL H[], int len, vector<Node> &pr) {
    for (int i = 0; i < len; i++) {
        for (int j = i; j < len; j++) {
            int value = calSingleSubH(H, i, j);
            pr.push_back(Node(value, j - i + 1, i));
        }
    }
}
//计算pr1和pr2中相同的hash值，维护最长子串
string getMax(string str1) {
    string str;
    int ans = 0;
    for (int i = 0; i < pr1.size(); i++) {
        for (int j = 0; j < pr2.size(); j++) {
            if (pr1[i].hashValue == pr2[j].hashValue) {
                if (pr1[i].length > ans) {
                    ans = pr1[i].length;
                    str = str1.substr(pr1[i].start, ans);
                }
            }
        }
    }
    return str;
}
int main() {
    string str1, str2;
    getline(cin, str1);
    getline(cin, str2);
    init(max(str1.length(), str2.length())); //初始化powP数组
    calH(H1, str1); //分别计算str1和str2的hash值
    calH(H2, str2);
    calSubH(H1, str1.length(), pr1); //分别计算所有H1[i…j]和H2[i…j]
    calSubH(H2, str2.length(), pr2);
    cout << getMax(str1) << endl; //输出最长公共子串
    return 0;
}
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