Pagini recente » Cod sursa (job #1043254) | Cod sursa (job #3288263) | Cod sursa (job #2953318) | Cod sursa (job #1799292) | Cod sursa (job #723792)
Cod sursa(job #723792)
#include <iostream>
#include <vector>
#include <climits>
#include <set>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <cstring>
#define NMAX 2000005
using namespace std;
char T[NMAX], P[NMAX];
int b[NMAX];
int pos[1000];
void citire(){
ifstream in("strmatch.in");
in >> P;
in >> T;
}
void compute_prefix(){
b[0] = -1;
int k = -1, i;
for(i = 0; i < strlen(P);){
while(k >= 0 && P[i] != P[k])
k = b[k];
++k, ++i;
b[i] = k;
}
}
int nr_apar = 0;
void scrie_sol(){
ofstream out("strmatch.out");
int i;
out << nr_apar << endl;
for(i = 0; i < nr_apar; ++i)
out << pos[i] << " ";
}
int main(){
citire();
compute_prefix();
int j = 0, i;
for(i = 0; i < strlen(T);){
while(j >= 0 && P[j] != T[i])
j = b[j];
++j, ++i;
if(j == strlen(P)){
pos[nr_apar] = i - strlen(P);
nr_apar++;
if(nr_apar == 1000)
goto scrie;
j = b[j];
}
}
scrie:
scrie_sol();
return 0;
}