Pagini recente » Cod sursa (job #1324418) | Cod sursa (job #663685) | Cod sursa (job #654259) | Cod sursa (job #856777) | Cod sursa (job #1324315)
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int nmax = 2000000;
const int max_sol = 1000;
int n, m;
char a[nmax+5], b[nmax+5];
int pi[nmax+5];
vector <int> sol;
void prefix()
{
pi[1] = 1;
int q = 0;
for(int i=2; i<=n; i++)
{
while(q && a[q+1] != a[i])
q=pi[q];
if(a[q+1] == a[i])
q++;
pi[i] = q;
}
}
void prefix2()
{
int q = 0;
for(int i=1; i<=m; i++)
{
while(q && a[q+1] != b[i])
q=pi[q];
if(a[q+1] == b[i])
q++;
if(q == n)
{
q=pi[n];
if(sol.size() < max_sol)
sol.push_back(i-n+1);
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s", a+1, b+1);
n=strlen(a+1);
m=strlen(b+1);
prefix();
prefix2();
printf("%d\n", sol.size());
for(int i=0; i<sol.size(); i++)
printf("%d ", sol[i]);
return 0;
}