Pagini recente » Cod sursa (job #1742276) | Cod sursa (job #287770) | Cod sursa (job #601920) | Cod sursa (job #3273953) | Cod sursa (job #973959)
Cod sursa(job #973959)
#include <cstdio>
#include <cstring>
using namespace std;
int key[2000005], na, nb, n;
char a[2000005], b[2000005];
int sol[1000000];
/*struct element
{
int inf;
element *urm;
element(int x = 0)
{
inf = x;
urm = NULL;
}
};
struct lista
{
element *root, *last;
}sol;
void push(lista &q, int val)
{
if(q.root == NULL)
{
q.root = new element(val);
q.last = q.root;
}
else
{
q.last -> urm = new element(val);
q.last = q.last -> urm;
}
}*/
void make_key()
{
key[0] = 0;
for(int i = 1; i < na; i++)
if(a[i] == a[key[i-1]+1] && i != key[i-1]+1)
key[i+1] = key[i] + 1;
else
key[i] = 0;
}
void solve()
{
int k = 0;
for(int i = 0; i <= nb; i++)
{
if(k)
{
if(k == na)
{
//n++;
//push(sol, i - na);
sol[n++] = i-na;
}
if(a[k] == b[i])
k++;
else
{
k = key[k];
i--;
}
}
if(!k)
{
k = 1;
while(b[i] != a[0] && i < nb)
i++;
}
}
}
void afis()
{
printf("%d\n", n);
/*for(element *p = sol.root; p; p = p -> urm)
printf("%d ", p -> inf);
printf("\n");*/
for(int i = 0; i< n; i++)
printf("%d ", sol[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s\n", a, b);
na = strlen(a);
nb = strlen(b);
make_key();
solve();
afis();
return 0;
}