Pagini recente » Cod sursa (job #481722) | Cod sursa (job #1287873) | Cod sursa (job #2659139) | Cod sursa (job #3202982) | Cod sursa (job #3264279)
#include <fstream>
#include <vector>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string s,s1;
int p[2000001];
vector<int> rasp;
void prec(){
int lung=0,i;
p[0]=0;
for(i=1;i<s.size();){
if(s[i]==s[lung]){
lung++;
p[i]=lung;
i++;
}else if(lung!=0){
lung=p[lung-1];
}else{
p[i]=0;
i++;
}
}
}
void kmp(){
int i,j;
i=j=0;
while(i<s1.size()){
if(s1[i]==s[j]){
i++;j++;
if(j==s.size()){
rasp.push_back(i-j);
j=p[j-1];
}
}else if(j!=0) j=p[j-1];
else i++;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int i;
cin>>s>>s1;
prec();
kmp();
cout<<rasp.size()<<"\n";
for(i=0;i<min((int)rasp.size(),1000);i++){
cout<<rasp[i]<<" ";
}
return 0;
}