字符串相关

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/

下午演示的一些函数和容器的用法还需要各位多加练习。