Pagini recente » Cod sursa (job #1011289) | Cod sursa (job #2153570) | Cod sursa (job #458025) | Cod sursa (job #2960938) | Cod sursa (job #1410614)
//#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 (dr<=i)
{
int j=i;
while (a[j]==a[j-i]) ++prf[i],++j;
if (prf[i]<=1) continue;
st=i,dr=i+prf[i]-1;
continue;
}
int l=prf[i-st+1];
if (l+i-1<dr)
{
prf[i]=l;
continue;
}
int j=min(i,dr-1);
while (a[j]==a[j-i]) ++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);
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;
}