Pagini recente » Cod sursa (job #2452359) | Cod sursa (job #147476) | Cod sursa (job #1375838) | Cod sursa (job #1209165) | Cod sursa (job #2755891)
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int mx=2e6+100;
string pat,tex;
int lps[mx];
void preprocess(){
int i=0,j=1;
lps[0]=0;
while(j<pat.length()){
if(pat[i]==pat[j]){
i++;
lps[j]=i;
j++;
}
else{
if(i==0){
lps[j]=0;
j++;
}
else{
i=lps[i-1];
}
}
}
}
void kmp(){
vector<int> result;
int i=0,j=0;
while(j<tex.length()){
if(pat[i]==tex[j]){
i++;
j++;
}
if(i==pat.length()){
result.push_back(j-(int)pat.length());
i=lps[i-1];
}
if(pat[i]!=tex[j]){
if(i==0){
j++;
}
else{
i=lps[i-1];
}
}
}
out<<result.size()<<endl;
int len=min((int) result.size(),1000);
for(int p=0;p<len;p++){
out<<result[p]<<" ";
}
}
void solve(){
in>>pat>>tex;
preprocess();
kmp();
}
int main(){
solve();
return 0;
}