Pagini recente » Cod sursa (job #483746) | Istoria paginii utilizator/susneamaria | Cod sursa (job #1292569) | Cod sursa (job #175052) | Cod sursa (job #2174489)
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int NMax = 2000005;
int pi[NMax];
char a[NMax], b[NMax];
int na, nb;
void Prefix()
{
int j=0;
for(int i=1; i<na; ++i)
{
while(j>0 && a[i]!=a[j])
j = pi[j-1];
if(a[i] == a[j])
++j;
pi[i] = j;
}
}
void KMP()
{
int potr = 0;
int sol[1005];
int j = 0;
for(int i=0; i<nb; ++i)
{
while(j>0 && b[i] != a[j])
j = pi[j-1];
if(b[i] == a[j])
++j;
if(j==na)
{
++potr;
if(potr==1000)
{
cout << potr << "\n";
for(int i=1; i<=potr; ++i)
cout << sol[i] << " ";
return;
}
else
{
sol[potr] = i - na + 1;
}
}
}
cout << potr << "\n";
for(int i=1; i<=potr; ++i)
cout << sol[i] << " ";
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", &a, &b);
na = strlen(a);
nb = strlen(b);
Prefix();
KMP();
return 0;
}