Pagini recente » Cod sursa (job #2890858) | Cod sursa (job #210901) | Cod sursa (job #782470) | Cod sursa (job #631057) | Cod sursa (job #1808801)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000010], B[2000010];
int q, prefix[2000010],LGa,LGb;
int n, poz[1024];
void make_prefix()
{
q=0;
for(int i=2; i<=LGa; i++)
{
while(q>0 && A[q+1]!=A[i])
q=prefix[q];
if(A[q+1]==A[i])
q++;
prefix[i]=q;
}
}
int main()
{
fin>>A>>B;
q=0;
LGa=0;
for(; (A[LGa] >= 'A' && A[LGa] <= 'Z') || (A[LGa] >= 'a' && A[LGa] <= 'z')
|| (A[LGa] >= '0' && A[LGa] <= '9'); ++LGa);
for(; (B[LGb] >= 'A' && B[LGb] <= 'Z') || (B[LGb] >= 'a' && B[LGb] <= 'z')
|| (B[LGb] >= '0' && B[LGb] <= '9'); ++LGb);
for(int i=LGa; i>0; i--)A[i]=A[i-1];
A[0]='#';
for(int i=LGb; i>0; i--)B[i]=B[i-1];
B[0]='#';
make_prefix();
q=0;
n=0;
for(int i=1; i<=LGb; i++)
{
while(q>0 && A[q+1]!=B[i])
q=prefix[q];
if(A[q+1]==B[i])
q++;
if(q==LGa)
{
q=prefix[LGa];
if(n<1000)
poz[++n]=i-LGa;
}
}
fout<<n<<'\n';
for(int i=1; i<=n; i++)
{
fout<<poz[i];
if(i!=n)
fout<<' ';
}
return 0;
}