Pagini recente » Cod sursa (job #1562162) | Cod sursa (job #628343) | Cod sursa (job #1388621) | Cod sursa (job #676430) | Cod sursa (job #1675138)
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int m,n,nr;
char a[2000001],b[2000001];
int pi[2000001],contor;
queue<int> coada;
void citire()
{
fin.get(a,2000001);
fin.get();
fin.get(b,2000001);
m=strlen(b);
n=strlen(a);
}
void calcul_prefixe()
{
int k,i;
k=0;
pi[1]=0;
for(i=2;i<=n;i++)
{
while(k>0 and (a[k]!=a[i-1]))
k=pi[k];
if(a[k]==a[i-1])
k++;
pi[i]=k;
}
}
void potrivire()
{
int i,q=0;;
for(i=1;i<=m;i++)
{
while(q>0 and (a[q]!=b[i-1]))
q=pi[q];
if(a[q]==b[i-1])
q++;
if(q==n)
{
contor++;
if(contor<=1000)
coada.push(i-n);
}
}
}
void afisare()
{
int maxi,x;
fout<<contor<<'\n';
while(!coada.empty())
{
x=coada.front();
fout<<x<<' ';
coada.pop();
}
}
int main()
{
citire();
calcul_prefixe();
potrivire();
afisare();
return 0;
}