Sakana~
0%

【数据结构OJ】实验5-串应用

发表于 分类于

粘一下代码，或许复习的时候要用？

（事实是根本不会再看第二遍

【数据结构OJ】实验5-串应用

A. DS串应用–KMP算法

next改一改就行

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
#include <bits/stdc++.h>

using namespace std;
int n, m;
string s, p;

void Next(string &p, vector<int> &ne){
    //ne[0] = -1;
    for (int i = 1, j = 0; i < n; i ++){
        while (j && p[i] != p[j])
            j = ne[j - 1];
        if (p[i] == p[j])
            j ++;
        ne[i] = j;
    }
}

void KMP (string &s, string &p, int begin){
    vector<int> ne(n);
    Next (p, ne);
    cout << "-1 ";
    for (int i = 0; i < n - 1; i++)     cout << ne[i] << ' ';   cout << endl;
    for (int i = begin, j = 0; i < m; i ++){
        while (j && s[i] != p[j])
            j = ne[j - 1];
        if (s[i] == p[j])
            j ++;
        if (j == n){
            cout << i - n + 2 << endl;
            j = ne[j - 1];
            return ;
        }
    }
    cout << "0\n";
}

void solve () {
    cin >> s >> p;
    n = p.size (), m = s.size ();
    KMP (s, p, 0);
}

int main () {
    int t;
    cin >> t;
    while (t --) {
        solve ();
    }
}

B. DS串应用—最长重复子串

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
#include<bits/stdc++.h>

using namespace std;

int match (string s) {
    int n = s.size ();
    if (n == 1)     return -1;

    string p, ans;
    for (int len = n / 2; len > 0; len --) { //枚举子串长度
		for (int i = 0; i < n - len;  i++) { //枚举子串起点
			p = s.substr(i, len);
			ans = s.substr(i + len); //在后面看看能不能找到重复串，起点保证了不交叉
			if (ans.find(p) != string::npos)	return len; //string::npos的值表示直到字符串末尾的所有字符
		}
	}
	return -1;
}

void solve () {
	string s;
    cin >> s;
    cout << match (s) << endl;
}

int main() {
	int t;
	cin >> t;
    while (t --) {
        solve ();
    }
}

C. DS串应用–串替换

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
#include <bits/stdc++.h>

using namespace std;
int n, m;

void Next(string &p, vector<int> &ne){
    for (int i = 1, j = 0; i < n; i ++){
        while (j && p[i] != p[j])
            j = ne[j - 1];
        if (p[i] == p[j])
            j ++;
        ne[i] = j;
    }
}

void KMP (string &s, string &p, int begin, string q){
    vector <int> ne(n);
    Next (p, ne);
    for (int i = begin, j = 0; i < m; i ++){
        while (j && s[i] != p[j])
            j = ne[j - 1];
        if (s[i] == p[j])
            j ++;
        if (j == n){
            for (int k = 0; k < i - n + 1; k++) cout << s[k];
            cout << q;
            for (int k = i + 1; k < m; k++) cout << s[k];
            cout << endl;
            // j = ne[j - 1];
            return ;
        }
    }
    cout << s << endl;
}

void solve () {
    string s, p, q;
    cin >> s >> p >> q;
    n = p.size (), m = s.size ();
    cout << s << endl;
    KMP (s, p, 0, q);

}

int main () {
    int t;
    cin >> t;
    while (t --) {
        solve ();
    }
}

D. 串应用- 计算一个串的最长的真前后缀

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
#include <bits/stdc++.h>

using namespace std;
int n;

void Next(string &p){
    vector <int> ne(n);
    for (int i = 1, j = 0; i < n; i ++){
        while (j && p[i] != p[j])
            j = ne[j - 1];
        if (p[i] == p[j])
            j ++;
        ne[i] = j;
    }
    int x = n - ne[n-1];
    if (x == n)     puts ("empty");
    else {
        for (int i = x; i < n; i++)     cout << p[i];
        cout << endl;
    }
}

void solve () {
    string p;
    cin >> p;
    n = p.size ();
    Next (p);
}

int main () {
    int t;
    cin >> t;
    while (t --) {
        solve ();
    }
}

E. 子串循环问题 (Ver. I)

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
#include <bits/stdc++.h>

using namespace std;
int n;

void Next(string &p){
    vector <int> ne(n);
    for (int i = 1, j = 0; i < n; i ++){
        while (j && p[i] != p[j])
            j = ne[j - 1];
        if (p[i] == p[j])
            j ++;
        ne[i] = j;
    }
    int x = n - ne[n-1];
    if (n % x == 0 && ne[n-1])	cout << "0\n";
    else	cout << x -  n % x << endl;
}

void solve () {
    string p;
    cin >> p;
    n = p.size ();
    Next (p);
}

int main () {
    int t;
    cin >> t;
    while (t --) {
        solve ();
    }
}

F. 可重叠子串 (Ver. I)

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
#include <bits/stdc++.h>

using namespace std;
int n, m;

void Next(string &p, vector<int> &ne){
    for (int i = 1, j = 0; i < n; i ++){
        while (j && p[i] != p[j])
            j = ne[j - 1];
        if (p[i] == p[j])
            j ++;
        ne[i] = j;
    }
}

void KMP (string &s, string &p, int begin){
    int ans = 0;
    vector <int> ne(n);
    Next (p, ne);
    for (int i = begin, j = 0; i < m; i ++){
        while (j && s[i] != p[j])
            j = ne[j - 1];
        if (s[i] == p[j])
            j ++;
        if (j == n){
            ans ++;
            j = ne[j - 1];
        }
    }
    cout << ans << endl;
}

void solve () {
    string s;
    int t;
    cin >> s >> t;
    m = s.size ();
    while (t --) {
        string p;
        cin >> p;
        cout << p << ":";
        n = p.size ();
        vector <int> ne (n);
        KMP (s, p, 0);
    }
}

int main () {
    int t;
    cin >> t;
    while (t --) {
        solve ();
    }
}

G. 方程解析（string)

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
#include <bits/stdc++.h>

using namespace std;

void print (string s, bool find) {
    if (!find)  cout << 0;
    else {
        cout << s;
        if (s.empty () || (s.size () == 1 && s[0] == '-'))  cout << 1;
    } 
}

string s;
void solve () {
    int n = s.size ();
    string a = "", b = "", c = ""; //三个系数
    bool f1 = false, f2 = false;

    //先找二次方
    int st = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '^') { //一定是二次方
            f1 = true;
            st = i + 2;
            for (int j = 0; j < i - 1; j++)  a = a + s[j];
            break;
        }
    }

    //一次
    if (st == -1)   st = 0;
    //cout << "st=" << st << endl;
    for (int i = st; i < n; i++) {
        if (s[i] == 'x') {
            f2 = true;
            break;
        }
    }

    print (a, f1), cout << ' ';
    if (!f2) {    
        cout << "0 ";
        if (st >= n)    cout << "0\n";
        else {
            for (int i = st; i < n; i++)    cout << s[i];
            cout << endl;
        }
    }
    else {
        int i;
        for (i = st; i < n; i++) {
            if (s[i] == 'x')    break;
            if (s[i] == '+')    continue;
            b = b + s[i];
        }
        print (b, f2), cout << ' ';
        i ++;
        if (i >= n) {
            cout << "0\n";
            return ;
        }
        for (; i < n; i++) {
            if (s[i] == '+')    continue;
            cout << s[i];
        }
        cout << endl;
    }
    // for (int i = n - 1; i >= st; i++) {
    //     if (s[i] == 'x') {
    //         f2 = true;
    //         for (int j = st; j < i; j++) {
    //             if (s[j] == '+')    continue;
    //             b = b + s[j];
    //         }
    //         st = i;
    //         break;
    //     }
    // }
  
}

int main () {
    while (cin >> s)    solve ();
}

//输出系数

总结：kmp + 乱搞