Pagini recente » Cod sursa (job #1695704) | Cod sursa (job #2419674) | Cod sursa (job #2063608) | Cod sursa (job #1730452) | Cod sursa (job #1604561)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
void mk_pi(const string& str, vector<int>& pi){
const int n = str.size();
pi.resize(n, 0);
for(int i = 1, v = 0; i < n; ++i){
for( ; str[v] != str[i] && v; v = pi[v-1]);
if(str[v] == str[i]){
++v;
}
pi[i] = v;
}
}
void do_strmatch(const string& caut, const string& str, int& nr, vector<int>& rez){
string s = caut;
s.push_back('#');
s.append(begin(str), end(str));
vector<int> pi;
mk_pi(s, pi);
for(int i = 0, j = caut.size()+1; j < pi.size(); ++i, ++j){
if(pi[j] == caut.size()){
++nr;
if(rez.size() < 1000){
rez.push_back(i-caut.size()+1);
}
}
}
}
int main(){
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string caut, str;
f >> caut >> str;
int nr=0;
vector<int> rez;
do_strmatch(caut, str, nr, rez);
g << nr << '\n';
for(int i = 0; i < rez.size(); ++i){
g << rez[i] << ' ';
}
return 0;
}