Pagini recente » Cod sursa (job #3230005) | Cod sursa (job #300614) | Cod sursa (job #3198893) | Cod sursa (job #894228) | Cod sursa (job #3157762)
#include <bits/stdc++.h>
#define NN 2000005
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char a[NN], b[NN];
int va[NN];
int pa;
int na, nb;
queue <int> q;
void make_prefix()
{
va[0] = 0;
pa = 0;
for(int i = 2 ; i <= na ; i++)
{
if(a[i] == a[pa+1])
pa++;
else
pa = 0;
va[i] = pa;
}
}
int main()
{
fin >> a + 1 >> b + 1;
na = strlen(a + 1);
nb = strlen(b + 1);
make_prefix();
pa = 0;
for(int i = 1 ; i <= nb ; i++)
{
if(b[i] == a[pa + 1])
{
pa++;
if(pa == na)
{
q.push(i - na + 1);
pa = va[pa] - 1;
i--;
continue;
}
}
else
pa = va[i];
}
fout << q.size() << '\n';
while(!q.empty())
{
fout << q.front() - 1 << " ";
q.pop();
}
return 0;
}