Pagini recente » Cod sursa (job #2309107) | Cod sursa (job #236317) | Cod sursa (job #2222351) | Cod sursa (job #1136838) | Cod sursa (job #2433805)
#include <iostream>
#include <fstream>
#include <vector>
class str_search{
std::string pattern,text;
std::vector<int>pos;
const static int d=256;
const static int MOD=881269;
public:
str_search(){}
str_search(std::string a,std::string b):pattern(a),text(b){}
void search(std::ofstream& out){
int th=0,ph=0,h=1;
for(int i=0;i<pattern.size()-1;i++)
h=(h*d)%MOD;
for(int i=0;i<pattern.size();i++)
th=(d*th+text[i])%MOD,ph=(d*ph+pattern[i])%MOD;
for(int i=0;i<text.size()-pattern.size()+1;i++){
if(th==ph){
bool ok=1;
for(int j=0;j<pattern.size();j++)
if(pattern[j]!=text[i+j]){
ok=0;
break;
}
if(ok)
pos.push_back(i);
}
th=(d*(th-text[i]*h)+text[i+pattern.size()])%MOD;
if(th<0)
th+=MOD;
}
out<<pos.size()<<'\n';
for(int i=0;i<pos.size();i++)
out<<pos[i]<<" ";
}
};
std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");
std::string pat,txt;
int main(){
in>>pat>>std::ws>>txt;
str_search(pat,txt).search(out);
return 0;
}