Pagini recente » Cod sursa (job #2227260) | Cod sursa (job #1980244) | Cod sursa (job #1490749) | Cod sursa (job #299245) | Cod sursa (job #2738721)
#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];
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;
vector<int> result;
while(j<text.length()){
if(pattern[i]==text[j]){
i++;
j++;
}
if(i==pattern.length()){
result.push_back(j-i);
if(result.size()==maximum){
break;
}
i=lps[i-1];
}
if(pattern[i]!=text[j]){
if(i!=0){
i=lps[i-1];
}
else j++;
}
}
out<<result.size()<<endl;
for(int k:result)
out<<k<<" ";
}
void solve(){
in>>pattern>>text;
preprocess();
kmp();
}
int main(){
solve();
return 0;
}