Pagini recente » Monitorul de evaluare | Cod sursa (job #288220) | Cod sursa (job #235953) | Cod sursa (job #2367527) | Cod sursa (job #2498569)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int NMAX = 2000001;
int lgT, lgP, n;
char T[NMAX], P[NMAX];
int pi[NMAX], pos[1001];
void prefix()
{
int k = 0;
pi[0] = 0;
int i = 1;
while(i < lgP)
if(P[i] == P[k])
{
k++;
pi[i] = k;
i++;
}
else if(k != 0)
k = pi[k - 1];
else
{
pi[i] = 0;
i++;
}
}
void kmp()
{
/// cu i ne deplasam in text
/// cu j ne deplasam in patern
int i = 0;
int j = 0;
prefix();
while(i < lgT)
{
if(T[i] == P[j])
{
i++;
j++;
}
if(j == lgP)
{
/// avem solutie
n++;
pos[n] = i - j;
j = pi[j - 1];
}
else if(i < lgT && T[i] != P[j])
if(j)
j = pi[j - 1];
else
i++;
}
}
int main()
{
f.getline(P, NMAX);
lgP = f.gcount() - 1;
f.getline(T, NMAX);
lgT = f.gcount() - 1;
kmp();
g << n << '\n';
int minn = min(1000, n);
for(int i = 1; i <= minn; i++)
g << pos[i] << ' ';
return 0;
}