「LOJ#103」子串查找 （Hash

 1 /*
 2 编号     题目     状态     分数     总时间     内存     代码 / 答案文件     提交者     提交时间
 3 #224544     #103. 子串查找    Accepted     100     550 ms     2228 KiB     C++ / 545 B     qwerta     2018-10-10 18:01:15
 4 */
 5 #include<iostream>
 6 #include<cstdio>
 7 using namespace std;
 8 int nxt[1000003];
 9 int main()
10 {
11     string s,t;
12     cin>>s>>t;
13     int k=-1;
14     nxt[0]=-1;
15     int lens=s.length(),lent=t.length();
16     for(int i=1;i<lent;++i)
17     {
18         while(k!=-1&&t[i]!=t[k+1])k=nxt[k];
19         if(t[i]==t[k+1])k++;
20         nxt[i]=k;
21     }
22     k=-1;
23     int ans=0;
24     for(int i=0;i<lens;++i)
25     {
26         while(k!=-1&&s[i]!=t[k+1])k=nxt[k];
27         if(s[i]==t[k+1])k++;
28         if(k==lent-1){ans++;}
29     }
30     cout<<ans;
31     return 0;
32 }

/*
编号     题目     状态     分数     总时间     内存     代码 / 答案文件     提交者     提交时间
#224464     #103. 子串查找    Accepted     100     589 ms     2228 KiB     C++ / 817 B     qwerta     2018-10-10 17:06:38
*/
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    //freopen("a.in","r",stdin);
    string a,b;
    cin>>a>>b;
    unsigned long long h=0,hb=0;
    int lena=a.length(),lenb=b.length();
    int mod=19260817,p=233;//膜数(bi~)
    //
    unsigned long long pown=1,base=p;
    int k=lenb-1;
    while(k)
    {
        if(k&1)
        pown=pown*base%mod;
        base=base*base%mod;
        k>>=1;
    }
    //
    for(int i=0;i<lenb;++i)
    hb=(hb*p+b[i])%mod;
    for(int i=0;i<lenb;++i)
    h=(h*p+a[i])%mod;
    int ans=0;
    if(hb==h)ans++;
    //cout<<h<<" "<<hb<<endl;
    for(int i=lenb;i<lena;++i)
    {
        h-=a[i-lenb]*pown%mod;
        h=((h+mod)*p+a[i])%mod;
        //cout<<h<<" "<<hb<<endl;
        if(h==hb)ans++;
    }
    cout<<ans;
    return 0;
}