字符串相关
NOIP中和字符串相关的通常只有输入输出部分
历年字符串相关题目:
- NOIP2012Vigenère密码
- NOIP2017时间复杂度
- NOIP2016玩具谜题
- NOIP2015子串
KMP
KMP学习:http://www.matrix67.com/blog/archives/115
NOI2014动物园:http://uoj.ac/problem/5
标程:
#include<cstdio>
#include<cstring>
using namespace std;
int nxt[1200000];
int T;
char str[1200000];
const long long mod=1000000007;
long long ans;
int S[1200000];
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%s",str+1);
int ll=strlen(str+1);
nxt[1]=0;
S[1]=1;
ans=1;
int p1=0,p2=0;
for (int i=2;i<=ll;i++)
{
while (p1!=0&&str[i]!=str[p1+1])
{
p1=nxt[p1];
}
if(str[i]==str[p1+1])p1++;
nxt[i]=p1;
S[i]=S[nxt[i]]+1;
while (p2!=0&&str[i]!=str[p2+1])
{
p2=nxt[p2];
}
if(str[i]==str[p2+1])p2++;
while (p2>i/2)p2=nxt[p2];
ans*=(S[p2]+1);ans%=mod;
}printf("%lld\n",ans);
}
return 0;
}
字符串hash
题目:http://acm.nflsoj.com/problem/33
题解:http://acm.nflsoj.com/blog/youyl/blog/41
标程:
#include<cstdio>
#include<cstring>
using namespace std;
const long long mod=1000000007;
const long long mul=131;
char str[1200000];
inline int solve()
{
int l=strlen(str+1);
int lb=1,rb=l,cnt=0;
long long hashl=0,hashr=0,mult=1;
while (lb<rb)
{
hashr+=mult*(str[rb]-'a'+1)%mod;
hashr%=mod;
hashl*=mul;hashl%=mod;
hashl+=(str[lb]-'a'+1);
hashl%=mod;
if(hashl==hashr)
{
hashl=0;
hashr=0;
mult=1;
cnt+=2;
}
else
{
mult*=mul;
mult%=mod;
}
lb++;
rb--;
}
if(lb==rb)cnt++;
if(lb!=rb&&hashl!=0)cnt++;
return cnt;
}
int T;
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%s",str+1);
printf("%d\n",solve());
}
return 0;
}
头文件相关
使用规则:http://www.noi.cn/about/rules/362-noi
全面的内容:http://www.cplusplus.com/reference/
下午演示的一些函数和容器的用法还需要各位多加练习。