Pagini recente » tema | Cod sursa (job #2676486) | Cod sursa (job #2585611) | Cod sursa (job #1195085) | Cod sursa (job #1502929)
#include<fstream>
#include<string>
#include<vector>
using namespace std;
string a,b;
int i,j,pref[2000005],k;
vector<int> sol;
void make_prefix(){
pref[0]=-1;
pref[1]=0;
for (i=2; i<a.length(); ++i){
int k=pref[i-1];
while (a[k+1]!=a[i] && k>=0) k=pref[k];
pref[i]=k+1;
}
}
int main(void) {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
getline(cin,a);
getline(cin,b);
a=" "+a;
b=" "+b;
make_prefix();
int nrapp=0;
k=1;
for (i=1; i<b.length(); ++i) {
while (b[i]!=a[k] && k>0) k=pref[k];
++k;
if (k==a.length()) {
k=pref[a.length()-1]+1;
++nrapp;
if (nrapp<=1000) sol.push_back(i-a.length()+1);
}
}
cout<<nrapp<<"\n";
for (i=0; i<sol.size(); ++i) cout<<sol[i]<<" ";
return 0;
}