Pagini recente » Cod sursa (job #2705288) | Cod sursa (job #2242329)
#include <fstream>
#include <vector>
#include <string>
#define NMAX 2000005
#define MAXAP 1005
using std::string;
using std::vector;
std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");
string text, pattern;
int v[NMAX], num_ap[MAXAP];
string shift_char(string text){
text += " ";
for(int i = text.size() - 1; i>=1; i--){
text[i] = text[i - 1];
}
text[0] = ' ';
return text;
}
void read_data(){
in >> pattern;
in >> text;
pattern = shift_char(pattern);
text = shift_char(text);
}
void pattern_vector(string& pattern, int v[]){
int m = pattern.size();
v[1] = 0;
int k = 0;
for(int i = 2; i<m; i++){
while(k > 0 && pattern[k + 1] != pattern[i]){
k = v[k];
}
if(pattern[k + 1] == pattern[i]){
k ++;
}
v[i] = k;
}
}
void kmp(string& text, string& pattern, int v[], int& ap){
pattern_vector(pattern, v);
int n = text.size();
int m = pattern.size();
int q = 0;
ap = 0;
for(int i = 1; i<n; i++){
while(q > 0 && pattern[q + 1] != text[i]){
q = v[q];
}
if(pattern[q + 1] == text[i]){
q ++;
}
if(q == m - 1){
if(ap < 1000){
ap ++;
num_ap[ap] = i - (m - 1);
}
q = v[q];
}
}
}
int main(){
read_data();
int ap;
kmp(text, pattern, v, ap);
out << ap << '\n';
for(int i = 1; i<=ap; i++){
out << num_ap[i] << ' ';
}
in.close();
out.close();
return 0;
}