Pagini recente » Diferente pentru voronoi intre reviziile 41 si 40 | Diferente pentru problema/sdo intre reviziile 34 si 33 | Cod sursa (job #2981718) | Cod sursa (job #1318245) | Cod sursa (job #2538065)
#include <fstream>
#include <string>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int positions[1000];
int pos_size = 0;
int prefix[2000000];
int main(){
string pat, str;
cin>>pat>>str;
if(pat.size() > str.size()){
cout<<"0\n";
}
prefix[0] = 0;
for(int x = 1, p = 0;x<pat.size();x++){
if(pat[x] == pat[p]){
p++;
prefix[x] = p;
}else{
if(p){
while(p)
p = prefix[p - 1];
prefix[x] = p;
}else prefix[x] = 0;
}
}
for(int x = 0, i = 0;x<str.size();){
if(str[x + i] != pat[i]){
if(i){
x = x + i - prefix[i - 1];
i = prefix[i - 1];
}else x++;
}else{
i++;
if(i == pat.size()){
positions[pos_size++] = x;
if(pos_size == 1000)
break;
x = x + pat.size() - prefix[pat.size() - 1];
i = prefix[pat.size() - 1];
}
}
}
cout<<pos_size<<'\n';
for(int x = 0;x<pos_size;x++){
cout<<positions[x]<<' ';
}
return 0;
}