KMP求调
  • 板块学术版
  • 楼主jzy_CSPJ_AK
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/19 17:03
  • 上次更新2024/11/19 19:17:28
查看原帖
KMP求调
1034698
jzy_CSPJ_AK楼主2024/11/19 17:03
#include<bits/stdc++.h>
using namespace std;
string a, b;
vector<int> nxt;

void get_nxt(string & s){
    int l = s.length(), j = 0, last = -1;
    nxt.resize(l);nxt[0] = -1;
    while(j < l){
        if(last == -1 || nxt[j] == nxt[last])nxt[++ j] = ++ last;
        else last = nxt[last];
    }
}

int KMP(string & s1, string & s2, vector<int> nxt){
    int i = 0, j = 0, l = s1.size(), ll = s2.size();
    while(i < l && j < ll){
        if(j == -1 || a[i] == a[j]) ++ i, ++ j;
        else j = nxt[j];
    }
    return (ll == j) ? (i - j) : -1;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> a >> b;
    get_nxt(b);
    int ans = KMP(a, b, nxt);
    if(ans == -1)cout << "no";
    else cout << "yes" << endl << ans;
    return 0;
}
2024/11/19 17:03
加载中...