Pagini recente » Cod sursa (job #1217947) | Cod sursa (job #1730551) | Cod sursa (job #1620354) | Cod sursa (job #2497297) | Cod sursa (job #407420)
Cod sursa(job #407420)
#include <string>
#include <vector>
#include <fstream>
using namespace std;
int main(){
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;in>>a>>b;
vector<int> gasiri;
vector<int> prefix (a.length(),0);
int k=-1;
for(int i=1;i<a.length();i++){
while(k>=0 and a[k+1]!=a[i]){
k=prefix[k];
}
if(a[k+1]==a[i]){
k++;
}
prefix[i]=k;
}
int q=-1;
for(int i=0;i<b.length();i++){
while(q>=0 and a[q+1]!=b[i]){
q=prefix[q];
}
if(a[q+1]==b[i]){
q++;
}
if(q+1==a.length()){
gasiri.push_back(i-a.length()+1);
}
}
out<<gasiri.size()<<endl;
for(int i=0;i<gasiri.size() and i<1000;i++){
out<<gasiri[i]<<" ";
}
}