Pagini recente » Cod sursa (job #433630) | Cod sursa (job #2866897) | Cod sursa (job #830964) | Cod sursa (job #617942) | Cod sursa (job #508758)
Cod sursa(job #508758)
#include <cstdio>
#include <fstream>
#include <cstring>
#define nmax 2000001
#define mmax 1000
using namespace std;
inline int minim(int a, int b)
{
if(a<b)
return a;
return b;
}
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
// FILE *fin = fopen("strmatch.in", "r");
// FILE *fout = fopen("strmatch.out", "w");
int m, n, t;
char s[nmax], p[nmax];
long sol[nmax], pi[nmax];
void prefix()
{
long i, k = -1;
for(i=1; i<n; ++i)
{
while((k>0) && p[k+1]!=p[i])
k = pi[k];
if(p[k+1] == p[i])
++k;
pi[i] = k;
}
}
int main()
{
fin.getline(p, nmax);
fin.getline(s, nmax);
n = strlen(p);
m = strlen(s);
prefix();
long i, k = -1;
for(i=0; i<m; ++i)
{
while((k>0) && s[i]!=p[k+1])
k=pi[k];
if(p[k+1] == s[i])
++k;
if(k==n-1)
{
++t;
if(t<=mmax)
sol[t] = i-n+1;
k = pi[k];
}
}
fout << t << "\n";
k = minim(t, 1000);
for(i=1; i<=k; ++i)
fout << sol[i] << " ";
return 0;
}