返回题解分享
讨论 / 题解分享/ 帖子详情

子串 - 题解

// https://dashoj.com/p/74
#include <bits/stdc++.h>

using namespace std;

int main() {
	string text, pattren;
	cin >> text >> pattren;
	string str = pattren + '#' + text;
	vector<int> pi(str.size(), 0);
	for (int i = 1; i < str.size(); i++) {
		int len = pi[i - 1];
		while (len != 0 && str[i] != str[len]) len = pi[len - 1];
		if (str[i] == str[len]) pi[i] = len + 1;
	}
	sort(pi.begin(), pi.end(), [](int a, int b) {
		return a > b;
	});
	int cnt = 0, max = pi[0];
	for (int i : pi) if (i == max) cnt++; else break;
	cout << cnt << endl;
	return 0;
}
0 回复 0 转发 0 喜欢 3 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!