Pagini recente » Cod sursa (job #1114547) | Cod sursa (job #1639796) | Cod sursa (job #2095706) | Cod sursa (job #194636) | Cod sursa (job #2382609)
#include <iostream>
#include <fstream>
#define MAX 2000010
#define AMAX 1010
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
int lps[MAX],N;
int ans[AMAX];
string p,s;
void calc_lps(string pat,int* lps){
lps[0]=0;
int la=0;
for(int i=1;i<pat.size();)
if(pat[i]==pat[la]){
lps[i]=++la;
i++;
} 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()){
N++;
if(N<=1000)ans[N]=i-j;
j=lps[j-1];
} else if(i<st.size()&&pat[j]!=st[i]){
if(j!=0)j=lps[j-1];
else i++;
}
}
}
int main()
{
f>>p>>s;
rez(s,p);
g<<N<<'\n';
for(int i=1;i<=min(N,1000);i++)g<<ans[i]<<" ";
f.close ();
g.close ();
return 0;
}