T250634 『JROI-7』PMK 配匹串符字

题目描述
对于一个字符串 \(S\)，记 \(|S|\) 表示 \(S\) 的长度，记 \(S_i\) 表示 \(S\) 的第 \(i\) 个字符，记 \(S_{l,r}\) 表示 \(S_l,S_{l+1},…,S_r\) 组成的字符串。定义两个字符串相等，当且仅当他们长度相等，且每个位置的字符相同。

对于一个字符串 \(S\) 和一个正整数 \(i\le |S|\)，若 \(k\) 是满足k<i\(S_{1,k}=S_{i-k+1,i}\) 的最大的正整数，则 \(next_i=k\)。特别的，若不存在 \(k\) 满足条件，则 \(next_i=0\)。

请你构造一个由小写字母组成的字符串 \(S\)，满足 \(|S|=n\)，且对于所有正整数 \(i\le |S|\)，\(next_i\) 之和最小。

题目就是让我们构造字符串使得其前缀自匹配的长度最小，那我们随意确定第一个字符，后面都不包含它即可。

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin>>n;
	cout<<(char)97;
	for(int i=1;i<n;i++) cout<<char(98);
	return 0;
}

原文地址：http://www.cnblogs.com/mrkou/p/16884424.html