Pagini recente » Cod sursa (job #419513) | Cod sursa (job #933137) | Cod sursa (job #3357343) | Cod sursa (job #230452) | Cod sursa (job #3342703)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int pi[2000003],n,poz[2000003],ct;
int main()
{
string a,b;
fin>>a>>b;
pi[0]=0;
n=a.size();
int lung_pref=0;
for (int i=1; i<n; i++)
{
while (lung_pref>0 && a[i]!=a[lung_pref])
{
lung_pref=pi[lung_pref-1];
}
if (a[i]==a[lung_pref])
{
lung_pref++;
}
pi[i]=lung_pref;
}
int m=b.size();
lung_pref=0;
for (int i=0; i<m; i++)
{
while (lung_pref>0 && b[i]!=a[lung_pref])
{
lung_pref=pi[lung_pref-1];
}
if (b[i]==a[lung_pref])
{
lung_pref++;
}
if (lung_pref==n)
{
ct++;
if (ct<=1000)
poz[ct]=i-n+1;
}
}
fout<<ct<<'\n';
for (int i=1; i<=ct; i++)
{
fout<<poz[i]<<" ";
}
return 0;
}