Pagini recente » Cod sursa (job #1128086) | Cod sursa (job #1568518) | Cod sursa (job #2145367) | Cod sursa (job #255944) | Cod sursa (job #2376489)
#include <iostream>
#include <fstream>
#include <cstring>
#define lim 2000005
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[lim], b[lim];
int v[lim], nou[lim], n, m, cate=0;
void read()
{
in.getline(a, lim);
in.getline(b, lim);
n=strlen(a);
m=strlen(b);
}
void parcurgere_a()
{
v[0]=0;
int i=1, j=0;
while(i<n)
{
if(a[i]==a[j])
{
v[i]=j+1;
++j;
}
else
{
while(j>0 && a[i]!=a[j])
j=v[j-1];
if(a[i]==a[j])
{
v[i]=j+1;
++j;
}
else
{
v[i]=0;
j=0;
}
}
++i;
}
}
void parcurgere_b()
{
int i=0, j=0;
while(i<m)
{
if(a[j]==b[i])
{
++j;
}
else
{
j=v[j];
}
if(j==n && cate<1000)
{
nou[++cate]=i-n+1;
j=v[j-1];
}
++i;
}
}
void afis()
{
out<<cate<<'\n';
for(int i=1; i<=cate; ++i)
out<<nou[i]<<" ";
}
int main()
{
read();
parcurgere_a();
parcurgere_b();
afis();
return 0;
}