实验3 串的实现

#include <iostream>
#include<string>
using namespace std;
const int N = 1e7 + 5;

struct strs {
    string st;
    int len;
}s,c,c1,c2;
int next1[N];

int mumo() {
    cout << "您可以进行一下操作：\n";
    cout << "1：将串S中所有其值为c1的字符换成c2的字符\n";
    cout << "2：将串S中所有字符逆序\n";
    cout << "3：从串S中删除其值等于c的所有字符\n";
    cout << "4：从串S中第i个字符起求出首个与字符串S1相同的子串的起始位置\n";
    cout << "其他：退出\n";
    int k; cin >> k;
    return k;
}

void ne(strs cc){
    next1[1] = 0; 
    for (int i = 2, j = 0; i <= cc.len; i++){
        while (j && cc.st[i] != cc.st[j + 1])
            j = next1[j];
        if (cc.st[i] == cc.st[j + 1]) j++; 
        next1[i] = j;
    }
}

int kmp(int p,strs ss,strs cc){
    ne(cc);
    for (int i = 1, j = 0; i <= ss.len; i++) {
        while (j && ss.st[i] != cc.st[j + 1]) j = next1[j];
        if (ss.st[i] == cc.st[j + 1]) j++;
        if (j == cc.len){
            if(i - cc.len+1>=p)
                return i - cc.len+1;
            else {
                j = next1[j];
                continue;
            }
        }
    }
  return -1;
}

void swap_ctr() {
    string k=""; int p = -c1.len,l;
    while (1) {
        l = p;
        p = kmp(p+c1.len, s, c1);
        if (p == -1) break;
        for (int i = l+c1.len; i < p; i++) 
            if(i!=0)
              k += s.st[i];
        for (int i = 1; i <= c2.len; i++)
            k += c2.st[i];
    }
    if(l<=s.len)
        for (int i = l+c1.len; i <=s.len; i++)
            if (i != 0)
                k += s.st[i];
    s.st = k; s.len = k.length();
    cout << "替换后S为：\n" << s.st << endl;
    s.st = ' ' + s.st;
}

void ni() {
    string k;
    for (int i = s.len; i > 0; i--)
        k += s.st[i];
    cout << "逆序后为：\n" << k << endl;
    s.st = ' ' + k;
}

void del_str() {
    string k = ""; int p = -c.len, l;
    while (1) {
        l = p;
        p = kmp(p + c.len, s, c);
        if (p == -1) break;
        for (int i = l + c.len; i < p; i++)
            if (i != 0)
                k += s.st[i];
    }
    if (l <= s.len)
        for (int i = l + c.len; i <= s.len; i++)
            if(i!=0)
               k += s.st[i];
    s.st = k; s.len = k.length();
    cout << "删除c后S为：\n" << s.st << endl;
    s.st = ' ' + s.st;
}

int main(){
   int k;
   cout << "请输入一个字符串 S ：\n";
   cin >> s.st; s.len = s.st.length();
   s.st = ' ' + s.st;
   do {
        k=mumo();
        switch (k)
        {
        case 1:
            cout << "请输入查找的字符串c1：\n";
            cin >> c1.st; c1.len = c1.st.length();
            c1.st = ' ' + c1.st;
            cout << "请输入要替换成的字符串c2：\n";
            cin >> c2.st; c2.len = c2.st.length();
            c2.st = ' ' + c2.st;
            swap_ctr();
            break;
        case 2:
            ni();
            break;
        case 3:
            cout << "请输入要删除的部分c：\n";
            cin >> c.st; c.len = c.st.length();
            c.st = ' ' + c.st;
            del_str();
            break;
        case 4:
            int i;
            cout << "请输入查找的起始位置（以1开始）：\n";
            cin >> i;
            cout << "请输入要查找的字串：\n";
            cin >> c.st; c.len = c.st.length();
            c.st = ' ' + c.st;
            cout << kmp(i, s, c) << endl;
            break;
        default:
            break;
        }
   } while (k > 0 && k < 5);
    return 0;
}