K匹配

牛牛是赫赫有名的字符串高手，现在牛牛发现了一种新的匹配方式。给定一个字符串 $S$ 和一个字符串 $T$ ，如果 $S$ 存在一个长度为 $k$ 的子串 $S_{l_1, l_1 + k - 1}$ 和 $T$ 的某个长度为 $k$ 的子串 $T_{l_2,l_2 + k - 1}$ 相等，那么我们就认为字符串 $S$ 和字符串 $T$ 是 $k$ 匹配的。比如字符串 $abacc$ 和字符串 $ddabackk$ 就是 $4$ 匹配的。

牛牛知道这种匹配方式之后就迫不及待的想要提出新的问题。给定一个长度为 $n$ 的字符串 $S$ 和一个长度为 $k$ 的字符串 $T$ ，现在牛牛想知道 $S$ 有多少个子串和 $T$ 是满足 $k$ 匹配的。

本场大样例下载

第一行两个整数 $n, k$ 分别表示字符串 $S$ 的长度和字符串 $T$ 的长度。

第二行一个长度为 $n$ 的字符串表示 $S$ 。

第三行一个长度为 $k$ 的字符串表示 $T$ 。

保证字符串 $S$ 和 $T$ 中只包含小写字母。

#include<bits/stdc++.h> using namespace std; long long n,k,c=-1,d,q,ans; string a,b; int main() { cin>>n>>k;cin>>a>>b; while(q>=0) { if(q=a.find(b,d)); if(q==-1)break; ans+=(n-q-k+1)*(q-c); c=q;d=q+1; }cout<<ans<<endl; }

详情