Pagini recente » Cod sursa (job #2798501) | Cod sursa (job #1563118) | Cod sursa (job #2183273) | Cod sursa (job #1536955) | Cod sursa (job #2217278)
#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[1001], nrap;
void calcul_prefix(char *S, int N)
{
int q = 0;
prefix[1] = 0;
for(int i = 2; i <= N; i++)
{
while(q > 0 && S[q] != S[i - 1])
q = prefix[q];
if(S[q] == S[i - 1])
q++;
prefix[i] = q;
}
}
void KMP(char *text, int T, char *pattern, int P)
{
int q = 0;
for(int i = 1; i <= T; i++)
{
while(q > 0 && pattern[q] != text[i - 1])
q = prefix[q];
if(pattern[q] == text[i - 1])
q++;
if(q == P && nrap < 1000)
ap[++nrap] = i - P;
}
}
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++)
out << ap[i] << ' ';
return 0;
}