Pagini recente » Cod sursa (job #3131626) | Cod sursa (job #2379937) | Cod sursa (job #789642) | Cod sursa (job #627663) | Cod sursa (job #1323457)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int n, i, m, j, prefix[2000005], a, k, f=0, c[1005];
char s[20000005], p[2000005];
void MakePrefix()
{
a=0;
prefix[1]=0;
for(j=2; j<=m; ++j)
{
while(a && p[a+1]!=p[j]) a=prefix[a];
if (p[a+1]==p[j]) ++a;
prefix[j]=a;
}
}
void solve()
{
int a=0;
for (int i = 1; i <= n; ++i)
{
while (a && p[a+1] != s[i])
a = prefix[a];
if (p[a+1] == s[i])
++a;
if (a == m)
{
a = prefix[m];
if (f < 1000)
c[f] = i-m;
f++;
}
}
}
void afisare()
{
int u1=0, u2=0;
cout<<f<<'\n';
if (f<1000) u1=1;
else u2=1;
for(i=0; i< (f*u1 + 1000*u2) ; ++i)
cout<<c[i]<<' '; cout<<'\n';
}
int main()
{
cin>>(p+1);
cin>>(s+1);
m = strlen (p+1) ;
n = strlen (s+1) ;
if (m>n)
cout<<"0"<<"\n";
else
{
MakePrefix();
solve();
afisare();
}
return 0;
}