Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #430864) | Monitorul de evaluare | Cod sursa (job #508747)
Cod sursa(job #508747)
#include <cstdio>
#include <fstream>
#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];
int sol[nmax], pi[nmax];
void prefix()
{
int 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();
int 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];
}
}
if(!t)
fout << 1 << "\n";
else
{
fout << t << "\n";
for(i=1; i<=minim(t, mmax); ++i)
fout << sol[i] << " ";
}
return 0;
}