Pagini recente » Diferente pentru preoji/clasament/11-12 intre reviziile 13 si 21 | Cod sursa (job #322495) | Istoria paginii utilizator/branzateona | Cod sursa (job #1269069) | Cod sursa (job #1604540)
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
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& rez, vector<int>& poz){
string s = caut;
s.append(str);
vector<int> pi;
mk_pi(s, pi);
for(int i = 0, j = caut.size(); j < pi.size(); ++i, ++j){
if(pi[j] >= caut.size()){
++rez;
if(poz.size() < 1000){
poz.push_back(i-caut.size()+1);
}
}
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string caut, str;
f >> caut >> str;
int rez = 0;
vector<int> poz;
do_strmatch(caut, str, rez, poz);
g << rez << '\n';
for(int i = 0; i < poz.size(); ++i){
g << poz[i] << ' ';
}
return 0;
}