Pagini recente » Cod sursa (job #819866) | Cod sursa (job #441585) | Cod sursa (job #972993) | Cod sursa (job #1217536) | Cod sursa (job #1409485)
///KMP ALGORITHM
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 2000004;
char a[NMAX], b[NMAX];
int sol[1004], lg, n, m, pi[NMAX];
inline void Prefix()
{
int k = 0;
pi[1] = 0;
for(int i=2;i<=n;++i)
{
while(k > 0 && a[k+1] != a[i])
k = pi[k];
if(a[k+1] == a[i])
++k;
pi[i] = k;
}
}
inline void Solve()
{
int k = 0;
for(int i=1;i<=m;++i)
{
while(k > 0 && a[k+1] != b[i])
k = pi[k];
if(a[k+1] == b[i])
++k;
if(k==n)
{
++lg;
if(lg <= 1000)
sol[lg] = i-n;
k = pi[k];
}
}
}
inline void Write()
{
printf("%d\n",lg);
lg = min(lg,1000);
for(int i=1;i<=lg;++i)
printf("%d ",sol[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",(a+1),(b+1));
n = strlen(a+1), m = strlen(b+1);
Prefix();
Solve();
Write();
return 0;
}