Pagini recente » Cod sursa (job #1611756) | Cod sursa (job #887354) | Cod sursa (job #1779474) | Cod sursa (job #1912781) | Cod sursa (job #1604581)
#include <fstream>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
void mk_z(const string& str, vector<int>& v){
const int n = str.size();
v.resize(n, 0);
int centru = 0, right = 0;
for(int i = 1; i < n; ++i){
if(i >= right){
int j = 0;
for( ; str[j] == str[i+j]; ++j);
v[i] = j;
centru = i;
right = i+j-1;
}
else{
const int val_omoloaga = v[i-centru];
if(i+val_omoloaga-1 < right){
v[i] = val_omoloaga;
}
else{
int j = right-i+1;
for( ; str[j] == str[i+j]; ++j);
v[i] = j;
centru = i;
right = i+j-1;
}
}
}
}
void do_strmatch(const string& caut, const string& str, int& nr, vector<int>& poz){
string s = caut;
s.push_back('#');
s.append(str);
vector<int> z;
mk_z(s, z);
for(int i = 0, j = caut.size()+1; j < z.size(); ++i, ++j){
if(z[j] == caut.size()){
++nr;
if(poz.size() < 1000){
poz.push_back(i);
}
}
}
}
int main(){
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string caut, str;
f >> caut >> str;
int nr = 0;
vector<int> poz;
do_strmatch(caut, str, nr, poz);
g << nr << '\n';
for(int i = 0; i < poz.size(); ++i){
g << poz[i] << ' ';
}
}