Pagini recente » Statistici Alexandra Irimia (AlexandraIrimia) | Cod sursa (job #2862336) | Cod sursa (job #889268) | Cod sursa (job #3150826) | Cod sursa (job #1232261)
#include <fstream>
#include <iostream>
#define MAX_MATCHES 1000
#define MAX_LENGTH 2000001
using namespace std;
int POSITIONS[MAX_MATCHES];
int PREFIX[MAX_MATCHES];
int n_matches;
void compute_prefix(string & P)
{
int m = P.length();
PREFIX[1] = 0;
for (int i = 1; i < m; ++i)
{
int k = PREFIX[i];
while (k > 0 && P[k] != P[i])
k = PREFIX[k];
if (P[k] == P[i])
k = k + 1;
PREFIX[i+1] = k;
}
}
void KMP(string & P, string & T)
{
compute_prefix(P);
int m = P.length();
int n = T.length();
int k = 0;
for (int i = 0; i < n; ++i)
{
while (k > 0 && P[k] != T[i])
k = PREFIX[k];
if (P[k] == T[i])
k = k + 1;
if (k == m)
{
POSITIONS[n_matches++] = i - m + 1;
k = PREFIX[k];
}
}
}
int main()
{
ifstream ifs("strmatch.in");
ofstream ofs("strmatch.out");
string A, B;
ifs >> A >> B;
KMP(A, B);
ofs << n_matches << "\n";
for (int i = 0; i < n_matches; ++i)
ofs << POSITIONS[i] << " ";
return 0;
}