Pagini recente » Cod sursa (job #2778982) | Cod sursa (job #2041608) | Cod sursa (job #274142) | Cod sursa (job #1629908) | Cod sursa (job #793750)
Cod sursa(job #793750)
#include <cstdio>
#include <cstring>
#define N 2000050
using namespace std;
int prefix[N];
char a[N];
char b[N];
int sol[1001];
int k =0;
void pref(char s[])
{
int length = strlen(s);
int i = 0;
int j = -1;
prefix[0] = -1;
while(i < length)
{
while( j >= 0 && a[i] != a[j])
{
j = prefix[j];
}
++i;
++j;
prefix[i] = j;
}
}
void kmp()
{
int length = strlen(a);
int lengthB = strlen(b);
int i =0;
int j = 0;
while (i < lengthB)
{
while(j>=0 && b[i] != a[j])
{
j = prefix[j];
}
i++;
j++;
if(j == length)
{
if(k < 1000)
sol[k++] = i-j;
else
k++;
j = prefix[j];
}
}
}
void afis()
{
printf("%d\n",k);
for(int i = 0; i < k && i < 1000 ;i++)
{
printf("%d ",sol[i]);
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",&a,&b);
pref(a);
kmp();
afis();
return 0;
}