Pagini recente » Cod sursa (job #7648) | ojii | Cod sursa (job #1041941) | Cod sursa (job #2099490) | Cod sursa (job #2726966)
//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() && nrSol--;apart.pop())
printf("%i ", apart.front());
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(A, 2000005, stdin);
fgets(B, 2000005, stdin);
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;
}