Pagini recente » Cod sursa (job #2001494) | Cod sursa (job #780738) | Cod sursa (job #2826999) | Cod sursa (job #2229779) | Cod sursa (job #2738726)
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<map>
#include<algorithm>
#include<set>
#include<deque>
#include<queue>
using namespace std;
const int mx=2e6+100;
const int maximum=1000;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string pattern,text;
int lps[mx],result[mx],cnt=0;
void preprocess(){
int i=0,j=1;
while(j<pattern.length()){
if(pattern[i]==pattern[j]){
i++;
lps[j]=i;
j++;
}
else{
if(i!=0){
i=lps[i-1];
}
else{
lps[j]=0;
j++;
}
}
}
}
void kmp(){
int i=0,j=0;
while(j<text.length()){
if(pattern[i]==text[j]){
i++;
j++;
}
if(i==pattern.length()){
result[cnt++]=j-i;
i=lps[i-1];
}
if(pattern[i]!=text[j]){
if(i!=0){
i=lps[i-1];
}
else j++;
}
}
out<<cnt<<endl;
int length=min(cnt,maximum);
for(i=0;i<length;i++)
out<<result[i]<<" ";
}
void solve(){
in>>pattern>>text;
preprocess();
kmp();
}
int main(){
solve();
return 0;
}