33分玄关求调
查看原帖
33分玄关求调
1198506
wo488楼主2024/10/16 22:04
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
void build_next(string patt, vector<int>& next) {
	next.push_back(0);
	int prefix_len = 0;
	int i = 1;
	while (i < patt.size()) {
		if (patt[prefix_len] == patt[i]) {
			prefix_len += 1;
			next.push_back(prefix_len);
			i++;
		}
		else {
			if (prefix_len == 0) {
				next.push_back(0);
				i++;
			}
			else
				prefix_len = next[prefix_len];
		}
	}
}
//8
//cabcabca
int main() {
	int n;
	scanf("%d", &n);
	string s1;
	int i;
	int x=0;
	cin >> s1;
	vector<int>next;
	
	build_next(s1, next);
	for (i = 0; i < n; i++) {
		if (next[i] == 0)
			++x;
		else
			break;
	}
			
	printf("%d", x);
}
2024/10/16 22:04
加载中...