Pagini recente » Cod sursa (job #3176316) | Cod sursa (job #2125135) | Cod sursa (job #3237414) | Cod sursa (job #1957073) | Cod sursa (job #2390865)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int N = 2000010;
char a[N],b[N];
int pr[N],n,m,cnt;
vector<int>sol;
void prefix(),kmp();
int main()
{
f>>a+1>>b+1;
n=strlen(a+1);
m=strlen(b+1);
prefix();
kmp();
g<<cnt<<'\n';
for(auto it:sol)
g<<it<<' ';
return 0;
}
void prefix()
{
int q=0;
for(int i=2;i<=n;i++)
{
while(q>0&&a[q+1]!=a[i])q=pr[q];
if(a[q+1]==a[i])q++;
pr[i]=q;
}
}
void kmp()
{
int q=0;
for(int i=1;i<=m;i++)
{
while(q>0&&a[q+1]!=b[i])q=pr[q];
if(a[q+1]==b[i])q++;
if(q==n)
{
cnt++;
if(cnt<=1000)
sol.push_back(i-n);
}
}
}