[每日一题2020.06.12]P3375 【模板】KMP字符串匹配

关于kmp : https://www.cnblogs.com/roccoshi/p/13096988.html

关于kmp, 想了很久, 我觉得不应该放在这里写, 另开一贴记录一下.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<int> getnext(string s) {

	vector<int> next;

	next.push_back(-1);

	int i = 0, j = -1;

	while(i < s.size()) {

		if(s[i] == s[j] || j==-1) {

			i++;

			j++;

			next.push_back(j);

		}

		else {

			j = next[j];

		}

	}

	return next;

}

vector<int> kmp(string s1, string s2) {	// kmp : 找出s2在s1中出现的位置(全部)

	vector<int> next = getnext(s2);

	vector<int> ans;

	int i = 0, j = 0; 	// i指s1, j指s2

	while(i < s1.size()) {

		if(s1[i] == s2[j] || j==-1) {

			if(j == s2.size()-1) {

				ans.push_back(i - j);

				j = next[j];

			}

			else {

				i++;

				j++;

			}

		}

		else {

			j = next[j];

		}

	}

	return ans;

}

int main(){

	ios::sync_with_stdio(false);

    cin.tie(0);

    string s;

    string s1;

    cin >> s >> s1;

    vector<int> ans = kmp(s,s1);

    vector<int> next = getnext(s1);

    for (int i = 0; i < ans.size(); ++i) {

    	cout << ans[i] + 1 << endl;

    }

    for (int i = 1; i < next.size(); ++i)

    {

    	cout << next[i] << " ";

    }

    return 0;

}

巴特西

[每日一题2020.06.12]P3375 【模板】KMP字符串匹配

最新文章

热门文章