Pagini recente » Cod sursa (job #1936228) | Cod sursa (job #1520184) | Cod sursa (job #2110791) | Cod sursa (job #556651) | Cod sursa (job #688083)
Cod sursa(job #688083)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define NMAX 2000005
char T[NMAX], P[NMAX];
int b[NMAX];
void citire(){
FILE * f = fopen("strmatch.in", "rt");
fscanf(f, "%s %s", P, T);
fclose(f);
}
void compute_prefix(){
b[0] = -1;
int k = -1;
for(unsigned i = 0; i < strlen(P);){
while(k >= 0 && P[i] != P[k])
k = b[k];
++k, ++i;
b[i] = k;
}
}
vector<int> aparitii;
void scrie_sol(){
FILE* f = fopen("strmatch.out", "wt");
fprintf(f, "%d\n", aparitii.size());
for(unsigned i = 0; i < aparitii.size(); ++i)
fprintf(f, "%d ", aparitii[i]);
fclose(f);
}
int main(){
citire();
compute_prefix();
int j = 0;
for(unsigned i = 0; i < strlen(T);){
while(j >= 0 && P[j] != T[i])
j = b[j];
++j, ++i;
if(j == strlen(P)){
aparitii.push_back(i - strlen(P));
j = b[j];
}
}
scrie_sol();
return 0;
}