Pagini recente » Cod sursa (job #2181843) | Cod sursa (job #2396040) | Cod sursa (job #2277246)
#include<fstream>
#include<string>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int p[2000200];
int q = 0, ans = 0, ans_v[2000200];
string pattern, text;
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
cin >> pattern >> text;
text = ' ' + text;
for(int i = 1; i <= text.size(); i++){
while(q && text[i] != pattern[q]){
q = p[q];
}
// for(int i = 0 ; i < text.size(); i++)
// cout << p[i] << " ";
//cout << "\n";
if(text[i] == pattern[q]){
q++;
if(q == pattern.size()){
q = p[q];
ans_v[ans] = i - pattern.size();
ans++;
}
}
p[i+1] = q;
}
cout << ans;
cout << "\n";
for(int i = 0 ; i < min(1000,ans); i++)
cout << ans_v[i] << " ";
}