Pagini recente » Cod sursa (job #2563439) | Cod sursa (job #2732322) | Cod sursa (job #2049358) | Cod sursa (job #2606128) | Cod sursa (job #2217276)
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int DIM = 2000001;
char text[DIM], pattern[DIM];
int T, P;
int prefix[DIM], ap[DIM], nrap;
void calcul_prefix(char *S, int N)
{
int q = -1;
prefix[0] = 0;
for(int i = 1; i < N; i++)
{
while(q > 0 && S[q + 1] != S[i])
q = prefix[q];
if(S[q + 1] == S[i])
q++;
prefix[i] = q;
}
}
void KMP(char *text, int T, char *pattern, int P)
{
int q = -1;
for(int i = 0; i < T; i++)
{
while(q > 0 && pattern[q + 1] != text[i])
q = prefix[q];
if(pattern[q + 1] == text[i])
q++;
if(q == P - 1)
ap[++nrap] = i - P + 1;
}
}
int main()
{
in.getline(pattern, DIM);
P = in.gcount() - 1;
in.getline(text, DIM);
T = in.gcount() - 1;
calcul_prefix(pattern, P);
KMP(text, T, pattern, P);
out << nrap << '\n';
for(int i = 1; i <= nrap && i <= 1000; i++)
out << ap[i] << ' ';
return 0;
}