Pagini recente » Cod sursa (job #2898330) | Cod sursa (job #2961982) | Cod sursa (job #67690) | Cod sursa (job #604036) | Cod sursa (job #1007384)
#include<cstdio>
#include<cstring>
using namespace std;
int vlp[2000002], poz[1002];
char A[2000002],B[2000002];
int lp; // last poz
void prelucrarea(int last)
{
while(A[lp + 1] != A[last] && lp > 0)
{
lp = vlp[lp];
}
if(A[lp + 1] == A[last])
++ lp;
}
void init(int nA)
{
int i;
for(i = 2; i <= nA; ++ i)
{
prelucrarea(i);
vlp[i] = lp;
}
}
void prelucrareb(int last)
{
while(A[lp + 1] != B[last] && lp > 0)
{
lp = vlp[lp];
}
if(A[lp + 1] == B[last])
++ lp;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int i, nA, nB, nrez = 0;
gets(A + 1);
nA = strlen(A + 1);
gets(B + 1);
nB = strlen(B + 1);
init(nA);
lp = 0;
for(i = 1; i <= nB; ++ i)
{
prelucrareb(i);
if(lp == nA)
{
lp = vlp[nA];
++ nrez;
if(nrez <= 1000)
poz[nrez] = i - nA;
}
}
printf("%d\n", nrez);
if(nrez > 1000)
nrez = 1000;
for(i = 1; i <= nrez; ++ i)
printf("%d ", poz[i]);
printf("\n");
return 0;
}