Pagini recente » Cod sursa (job #189157) | Cod sursa (job #850837) | Cautari ortogonale | Cod sursa (job #1405086) | Cod sursa (job #1410649)
//#include <iostream>
#include <fstream>
using namespace std;
#define LE 4000666
#define cout g
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int prf[LE];
string a,s1,s2;
void solve(int N)
{
int st=-1,dr=-1,i;
for(i=1; i<N; ++i)
{
if (i==8)
bool okz=true;
if (dr<=i)
{
int j=i;
while (a[j]==a[j-i]&&j<N)
++prf[i],++j;
if (prf[i]<=1) continue;
st=i,dr=i+prf[i]-1;
continue;
}
int l=prf[i-st];
if (l+i-1<dr)
{
prf[i]=l;
continue;
}
int j=min(i,dr-1);
while (a[j]==a[j-i]&&j<N) ++j;
prf[i]=(j-i);
st=i,dr=j-1;
}
}
int main()
{
f>>s1>>s2;
a=s1+s2+" ";
int N=a.size();
int i;
solve(N);
// for(i=0;i<N;++i) cout<<prf[i]<<" ";
// cout<<'\n'<<'\n';
int n1=s1.size();
int nr_sol=0;
for(i=n1; i<N; ++i)
{
if (prf[i]<n1) continue;
++nr_sol;
}
int nrc=0;
cout<<nr_sol<<'\n';
for(i=n1; i<N; ++i)
{
if (prf[i]<n1) continue;
++nrc;
if (nrc>1000) break;
cout<<i-n1<<" ";
}
return 0;
}