Pagini recente » Cod sursa (job #499702) | Cod sursa (job #522766) | Borderou de evaluare (job #543669) | Cod sursa (job #15073) | Cod sursa (job #2063111)
#include <cstdio>
#include <cstring>
using namespace std;
char sub[2000005],str[2000005];
int pattern[2000005];
int len1, len2;
int rezultate[2000005], NrRez=0;
void makePattern()
{
int x = 0, y = 1;
pattern[0] = 0;
while(y < len1)
{
if(sub[x] == sub[y])
{
pattern[y] = x + 1;
x++;
y++;
}
else
if(x == 0)
y++;
else
{
x = pattern[x - 1];
while(x > 0)
{
if(sub[x] != sub[y])
x = pattern[x - 1];
else
{
pattern[y] = x + 1;
y++;
break;
}
}
}
}
}
void searchPattern()
{
int x=0, y=0;
while( y < len2)
{
if(sub[x] == str[y])
{
x++;
y++;
}
else
if(x != 0)
x = pattern[x-1];
else
y++;
if(x == len1)
rezultate[NrRez++] = y - len1;
}
printf("%d\n", NrRez);
if(NrRez > 1000)
NrRez = 1000;
for(int i = 0; i < NrRez; i++)
printf("%d ", rezultate[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", sub, str);
len1=strlen(sub);
len2=strlen(str);
makePattern();
searchPattern();
return 0;
}