Pagini recente » Cod sursa (job #364507) | Cod sursa (job #3246092) | Cod sursa (job #498581) | Cod sursa (job #2869103) | Cod sursa (job #2716498)
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N = 2000002;
char a[N], b[N];
int pi[N];
int rasp[N];
int main()
{
in>>(1+a)>>(1+b);
int lung = 0;
int m=strlen(1+a);
int n=strlen(1+b);
pi[1] = 0;
for(int i=2; i<=m; i++)
{
while(lung > 0 && a[i]!=a[lung+1])
{
lung = pi[lung];
}
if(a[i]==a[lung+1])
{
lung++;
}
pi[i]=lung;
}
/*
for(int i=1; i<=m; i++)
cout<<pi[i]<<' ';
*/
lung =0;
int k=0;
for(int i=1; i<=n; i++)
{
while(lung>0 && b[i]!=a[lung+1])
{
lung=pi[lung];
}
if(b[i]==a[lung+1])
{
lung++;
}
if(lung==m)
rasp[++k]=i-lung;
}
out<<k<<'\n';
for(int i=1; i<=k; i++)
out<<rasp[i]<<' ';
return 0;
}