T2的另一种做法

T2的std用了kmp，但是我在场上做题时没想到用这种算法（其实是太菜了不会）（划掉
我的思路是对两个字符串都跑一遍hash，再用hash找出第一个字符串中的匹配位置，将每个相等子串左右两边将没有计算过的(字符串长度+1)乘起来累加到答案中。
这样说起来可能不太清楚，可以尝试自己把字符串写下来，再配合代码食用。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define ha 10000010
using namespace std;
typedef unsigned long long ll;
int len1,len2;
char s1[ha],s2[ha];
ll hsh[ha],hsh2[ha];
ll hshlen[ha];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>len1>>len2;
    cin>>(s1+1);
    cin>>(s2+1);
    hshlen[0]=1;
    for(int i=1;i<=len1;++i){
        hsh[i]=hsh[i-1]*131+(s1[i]-'a'+1);
        hshlen[i]=hshlen[i-1]*131;
    }
    for(int i=1;i<=len2;++i){
        hsh2[i]=hsh2[i-1]*131+(s2[i]-'a'+1);
    }
    ll ans=0;
    int cnt=0,lst=0;
    for(int i=1;i+len2-1<=len1;++i){
        if(hsh[i+len2-1]-hsh[i-1]*hshlen[len2]==hsh2[len2]){
            ++cnt;
            ll lft=i-1-lst;
            ll rit=len1-(i+len2-1);
            ans+=(lft+1)*(rit+1);
            lst=i;
        }
    }
    cout<<ans<<endl;
    return 0;
}