Pagini recente » Cod sursa (job #2075755) | Cod sursa (job #399184) | Cod sursa (job #510038) | Cod sursa (job #894389) | Cod sursa (job #950505)
Cod sursa(job #950505)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
#define uint unsigned
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define NMAX 2000000
#define max(x,y) ((x>y)?(x):(y))
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(j < strlen(P) && P[i]==P[j]) {
//It's a match:
p[i] = j;
j++;
} else {
//Not a match:
p[i] = -1;
j=0;
}
}
}
void KMP() {
uint lengthP = strlen(P), lengthA = strlen(A);
uint i,j;
j = 0;
i = 0;
while(i < lengthA - lengthP + 1) {
while(p[j] != -1 && P[j] != A[i+j]) {
j = p[j];
}
while(j < lengthP && A[i+j] == P[j]) {
++j;
}
if(j == strlen(P)) {// we have yet another sollution
v.push_back(i);
--j;
}
j=max(p[j], 0);
i+=j+1;
}
}
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;
}