Pagini recente » Cod sursa (job #1986045) | Cod sursa (job #520425) | Cod sursa (job #1273353) | Cod sursa (job #578935) | Cod sursa (job #950648)
Cod sursa(job #950648)
#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 S[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;
}
}
// for(i=0;i<strlen(P);i++) g<<p[i]<<" ";g<<"\n";
}
void KMP() {
int lengthP = strlen(P), lengthS = strlen(S);
int i,j;
j = -1;
i = 0;
while(i < lengthS - lengthP + 1) {
while(j!= -1 && P[j+1] != S[i]) {
j = p[j];
}
while(i < lengthS && j+1 < lengthP && S[i] == P[j+1]) {
++j;
++i;
}
if(j == lengthP - 1) {// we have a solution
v.push_back(i-j-1);
j = p[j];
//++i;
} else {
//g<<"I am here";
i++;
j=-1;
}
//g<<i<<" "<<j<<"\n";
}
//g<<"\n";
}
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(S, NMAX);
if(strlen(P)<=strlen(S)) {
prefix();
KMP();
}
print_solutions();
return 0;
}