Pagini recente » Cod sursa (job #1831218) | Cod sursa (job #1669438) | Cod sursa (job #446392) | Cod sursa (job #1364274) | Cod sursa (job #1830839)
#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();
// for(int i = 0; i < len1; i++)
// {
// printf("%d ", pattern[i]);
// }
return 0;
}