Pagini recente » Profil Djok | Cod sursa (job #13078) | Cod sursa (job #1517015) | Cod sursa (job #2134591) | Cod sursa (job #949614)
Cod sursa(job #949614)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
#define uint unsigned
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define NMAX 2000000
char A[NMAX],P[NMAX];
int p[NMAX];
vector<int> v;
//Prefix vector:
void prefix() {
uint i,j;
p[0] = -1;
for(j=0,i=1; i<strlen(P); i++) {
if(P[i]==P[j]) {
//It's a match:
p[i] = j;
j++;
} else {
//Not a match:
p[i] = -1;
j=0;
}
}
/* for(i=0; i<strlen(P); i++) g<<P[i];
g<<"\n";
for(i=0; i<strlen(P); i++) g<<p[i];
g<<"\n";*/
}
void KMP() {
uint i,j;
for(j=0, i=0; i < strlen(A) - strlen(P) + 1; i++) {
while(P[j] != A[i+j] && p[j] != -1) {
j = p[j];
}
while(j < strlen(P) && A[i+j] == P[j]) {
++j;
}
if(j == strlen(P)) {// we have yet another sollution
v.push_back(i);
} else
j = 0;
}
}
void print_solutions() {
g<<v.size()<<"\n";
for(uint i=0; i < v.size(); i++)
g<<v[i]<<" ";
}
int main() {
f.getline(P, NMAX);
f.getline(A, NMAX);
prefix();
KMP();
print_solutions();
return 0;
}