Pagini recente » Cod sursa (job #2709558) | Cod sursa (job #1902302) | Cod sursa (job #251031) | Cod sursa (job #2791142) | Cod sursa (job #1471377)
#include <cstdio>
#include <cstring>
#define NMAX 2000007
using namespace std;
FILE *fin, *fout;
char A[NMAX], B[NMAX];
int pi[NMAX], ans[NMAX], ct = 1, sze1, sze2;
void citire()
{
scanf("%s%s", A + 1, B + 1);
}
void prefix()
{
sze1 = strlen(A + 1);
int k = 0;
pi[1] = 0;
for(int i = 2; i<= sze1; ++i)
{
while(A[k + 1] != A[i] && k) k = pi[k];
if(A[k + 1] != A[i]) k = 0;
else ++k;
pi[i] = k;
}
}
void KMP()
{
sze2 = strlen(B + 1);
int k = 0;
for(int i = 1; i<= sze2; ++i)
{
while(k && B[i] != A[k+1]) k = pi[k];
if(B[i] == A[k+1]) ++k;
if(k == sze1)
{
ans[ct] = i - sze1;
ct++;
}
}
}
void afisare()
{
printf("%d\n", ct - 1);
for(int i = 1; i< ct; ++i) printf("%d ", ans[i]);
printf("\n");
}
int main()
{
fin = freopen("strmatch.in", "r", stdin);
fout = freopen("strmatch.out", "w", stdout);
citire();
prefix();
KMP();
afisare();
fclose(fin);
fclose(fout);
return 0;
}