Pagini recente » Cod sursa (job #722534) | Cod sursa (job #1633405) | Cod sursa (job #1661307) | Cod sursa (job #473388) | Cod sursa (job #3157773)
#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] = -1;
pa = -1;
for(int i = 1 ; i < na ; i++)
{
if(a[i] == a[pa+1])
pa++;
else
pa = 0;
va[i] = pa;
}
}
int main()
{
fin >> a >> b;
na = strlen(a);
nb = strlen(b);
make_prefix();
pa = -1;
for(int i = 0 ; i < nb ; i++)
{
if(b[i] == a[pa + 1])
{
pa++;
if(pa == na - 1)
{
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() << " ";
q.pop();
}
return 0;
}