Pagini recente » Cod sursa (job #522535) | Cod sursa (job #2537887) | Cod sursa (job #3001785) | Cod sursa (job #2574675) | Cod sursa (job #2416574)
#include <iostream>
#include <fstream>
#define MAX 2000010
using namespace std;
int nra;
int lps[MAX],ans[MAX];
string a,b;
void calc_lps(string pat,int lps[MAX]){
lps[0]=0;
int la=0;
for(int i=1;i<pat.size();)
if(pat[i]==pat[la])lps[i++]=++la;
else
if(la!=0)la=lps[la-1];
else lps[i++]=0;
}
void rez(string st,string pat){
calc_lps(pat,lps);
for(int i=0,j=0;i<st.size();){
if(st[i]==pat[j])i++,j++;
if(j==pat.size()){
nra++;
if(nra<=1000)ans[nra]=i-j;
j=lps[j-1];
} else if(i<st.size()&&st[i]!=pat[j]){
if(j!=0)j=lps[j-1];
else i++;
}
}
}
int main()
{
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
f>>a>>b;
rez(b,a);
g<<nra<<'\n';
for(int i=1;i<=min(1000,nra);i++)g<<ans[i]<<" ";
f.close ();
g.close ();
return 0;
}