Pagini recente » Cod sursa (job #1458836) | Cod sursa (job #898857) | Istoria paginii runda/vvvvvv | Cod sursa (job #532870) | Cod sursa (job #1502947)
#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 (k>=0 && a[k+1]!=a[i]) 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();
/*for (i=1; i<a.length(); ++i) {
cout<<pref[i]<<" ";
}
return 0; */
int nrapp=0;
k=0;
for (i=1; i<b.length(); ++i) {
while (k>0 && b[i]!=a[k+1]) k=pref[k];
if (b[i]==a[k+1]) ++k;
if (k==a.length()-1) {
k=pref[k];
++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;
}