Pagini recente » Cod sursa (job #403892) | Cod sursa (job #1961631) | Cod sursa (job #2263196) | Cod sursa (job #2060969) | Cod sursa (job #957589)
Cod sursa(job #957589)
#include <cstring>
#include <fstream>
#include <algorithm>
using namespace std;
#define MAXN 2000005
char X[MAXN], Y[MAXN];
int Pi[MAXN], d[MAXN], K, N, M, pos[1024], n=0;
void constructie_pi()
{
K=0; // iteratorul K care ne ajuta la contructia lui Pi
Pi[1]=0; // Pi[i] < i => Pi[1] = 0
for (int i=2; i<=M; ++i)
{
while ( K && X[i]!=X[K+1] ) // cat timp prefixul nu este nul si literele
K=Pi[K]; // nu coincid sar din K in Pi[K]
if ( X[i]==X[K+1] ) K++; // daca literele coicid
Pi[i]=K;
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>X; f>>Y; N=strlen(Y); M=strlen(X);
for (int i = M; i; --i) X[i] = X[i-1]; X[0] = ' ';
for (int i = N; i; --i) Y[i] = Y[i-1]; Y[0] = ' ';
constructie_pi(); K=0;
for (int i=1; i<=N; ++i)
{
while (K && Y[i]!=X[K+1]) K=Pi[K]; // cat timp prefixul nu este nul si literele nu coincid sar din K in Pi[K]
if (Y[i]==X[K+1]) K++;
if (K==M)
{
K=Pi[M]; ++n;
if (n<=1000) pos[n]=i-M;
}
}
g<<n<<'\n';
for (int i=1; i<=min(n, 1000); ++i) g<<pos[i]<<' '; g<<'\n';
return 0;
}