Pagini recente » Cod sursa (job #1354306) | Cod sursa (job #9820) | Cod sursa (job #2928348) | Cod sursa (job #2492780) | Cod sursa (job #2106236)
//KMP
#include<cstring>
#include<cstdio>
using namespace std;
int i,k,urmator[1001];
char p[101],t[1001];
void prefix()
{
k=0;
urmator[1]=0;
for(i=2;i<=strlen(p);i++)
{
while(k>0&&p[i]!=p[k+1])
k=urmator[k];
if(p[i]==p[k+1])
k++;
urmator[i]=k;
}
}
int main()
{
freopen("p.in","r",stdin);
freopen("p.out","w",stdout);
gets(t+1);
t[0]='*';
gets(p+1);
p[0]='*';
prefix();
k=0;
for(i=2;i<=strlen(t);i++)
{
while(k>0&&p[k+1]!=t[i])
k=urmator[k];
if(p[k+1]==t[i])
k++;
if(k==strlen(p)-1)
{
printf("%d\n",i-strlen(p)+2);
k=urmator[k];
}
}
return 0;
}