Pagini recente » Cod sursa (job #100485) | Cod sursa (job #122786) | Cod sursa (job #2634760) | Cod sursa (job #370732) | Cod sursa (job #2726914)
//Ilie Dumitru
#include<cstdio>
#include<cstring>
#include<queue>
char A[2000005], B[2000005];
int lengthA, lengthB, nrSol;
int pref[2000005];
std::queue<int> apart;
void calcPrefix()
{
int k=-1, q;
pref[0]=-1;
for(q=1;q<lengthA;++q)
{
while(A[k+1]!=A[q] && k!=-1)
k=pref[k];
if(A[k+1]==A[q])
++k;
pref[q]=k;
}
}
void solve()
{
int k=-1, q;
calcPrefix();
for(q=0;q<lengthB;++q)
{
while(A[k+1]!=B[q] && k!=-1)
k=pref[k];
if(A[k+1]==B[q])
++k;
if(k==lengthA-1)
{
apart.push(q-k);
++nrSol;
k=pref[k];
}
}
printf("%i\n", nrSol);
for(;!apart.empty();apart.pop())
printf("%i ", apart.front());
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(A);
gets(B);
fclose(stdin);
lengthA=strlen(A);
lengthB=strlen(B);
if(A[lengthA-1]=='\n')
A[--lengthA]=0;
if(B[lengthB-1]=='\n')
B[--lengthB]=0;
solve();
fclose(stdout);
return 0;
}