Pagini recente » Borderou de evaluare (job #1496336) | Cod sursa (job #2815587) | Cod sursa (job #1084382) | Cod sursa (job #1309552)
//#include <iostream>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define LE 4000666
#define cout g
int M[LE];
string S,s2;
void Zalg(int n1)
{
int N=S.length();
int st=0,dr=0,i;
for(i=1; i<N; ++i)
{
int j=i;
if (dr>i)
{
j+=M[i-st];
j=min(j,dr);
}
for(; j<N&&j-i<n1&&j<N&&S[j]==S[j-i]; ++j)
bool te=true;
M[i]=j-i;
if (j-1>dr&&j-1>=i) st=i,dr=j-1;
}
}
int main()
{
f>>S>>s2;
int N1=S.length();
int N2=s2.length();
S+=s2;
int N=S.length();
Zalg(N1);
int nr_sol=0,i;
for(i=N1; i<N; ++i)
if (M[i]>=N1)
++nr_sol;
int still=0;
cout<<nr_sol<<'\n';
for(i=N1; i<N; ++i)
{
if (M[i]<N1) continue;
cout<<i-N1<<" ";
++still;
if (still==1000) break;
}
return 0;
}