Pagini recente » Cod sursa (job #548419) | Cod sursa (job #1354782) | Cod sursa (job #186325) | Cod sursa (job #2542948) | Cod sursa (job #3157644)
#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;
int main()
{
fin >> a >> b;
na = strlen(a);
nb = strlen(b);
pa = -1;
va[0] = -1;
for(int i = 1 ; i < na ; i++)
{
if(a[pa + 1] == a[i])
pa++;
else
pa = -1;
va[i] = pa;
}
pa = -1;
for(int i = 0 ; i < nb ; i++)
{
if(b[i] == a[pa + 1])
{
if(pa + 1 == na - 1)
{
q.push(i - na + 1);
pa = va[pa + 1] - 1;
i--;
continue;
}
pa++;
}
else
pa = -1;
}
fout << q.size() << '\n';
while(!q.empty())
{
fout << q.front() << " ";
q.pop();
}
return 0;
}