Pagini recente » Cod sursa (job #1512452) | Cod sursa (job #476) | Cod sursa (job #987928) | Cod sursa (job #1959826) | 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;
}