[TIOJ 1735] k-口吃子字串

原題連結
嗚姆....這題還算基本的趣題，我想到兩個作法。
第一眼看到很直覺的認為：啊這不就hash嗎！？
毫無懸念的寫下去，獲得了AC

code:

#define LL long long
#include<cstdio>
#include<cstring>
using namespace std;
const LL q=1000000007,p=23;
const LL maxn=100000+5;
char s[maxn];
LL power[maxn],hash[maxn];
int gethash(int L,int R)
{
    return((hash[R]-(power[R-L+1]*hash[L-1])%q)%q+q)%q;
}
int main()
{
    power[0]=1;
    for(int i=1;i<maxn;i++) power[i]=(power[i-1]*p)%q;
    int k;
    while(scanf("%d%s",&k,s+1)==2)
    {
        int n=strlen(s+1),ans=0;
        hash[0]=0;
        for(int i=1;i<=n;i++)
        {
            hash[i]=(p*(hash[i-1])+s[i])%q;
            if(i>=2*k-1 && gethash(i-2*k+1,i-k)==gethash(i-k+1,i))ans++;
        }
        printf("%d\n",ans);
    }
}

後來多想了一下，想要往KMP或是Z algorithm那方面去思考，發現怎麼弄模型都弄不太出來，google了一下題解，我真的被自己的愚蠢給驚呆了～

因為題目已經給定k，所以我們只要看所有位置i是否s[i+k-1]=s[i]，有的話設成1，否則為0。答案就是出現連續k個1的位置數量～～

唉，必須承認腦袋鈍化只想得到hash......

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+5;
char s[maxn];
int pre[maxn];
int main()
{
    int k;
    while(scanf("%d%s",&k,s+1)==2)
    {
        int ans=0,n=strlen(s+1);
        for(int i=1;i<=n;i++)
        {
            if(i+k<=n && s[i]==s[i+k]) pre[i]=pre[i-1]+1;
            else pre[i]=pre[i-1];
            if(i>=k && pre[i]-pre[i-k]==k) ans++;
        }
        printf("%d\n",ans);
    }
}