Pagini recente » Cod sursa (job #981112) | Utilizatori inregistrati la FMI No Stress 9 Warmup | Cod sursa (job #3168800) | Cod sursa (job #2359770) | Cod sursa (job #3195112)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
int tabel[2000001];
int n,m;
queue<int>q;
int ans=0;
int main()
{
int k=0,i=1;
fin>>a>>b;
n=a.size();
m=b.size();
while(i<n)
{
if(a[i]==a[k])
{
k++;
tabel[i]=k;
i++;
}
else if(k!=0) { k = tabel[k-1]; }
else
{
tabel[i] = 0;
i++;
}
}
k=0;
i=0;
while(i<=m)
{
if(b[i]==a[k])
{
i++;
k++;
if(k==n)
{
ans++;
if(ans<=1000)
q.push(i-n);
k=tabel[k-1];
}
}
else {
if(k!=0)
k=tabel[k-1];
else i++;
}
}
fout<<ans<<'\n';
while(!q.empty())
{
fout<<q.front()<<" ";
q.pop();
}
return 0;
}