Pagini recente » Cod sursa (job #96514) | Istoria paginii runda/guta_contest2/clasament | Istoria paginii runda/contest_5/clasament | Cod sursa (job #2008786) | Cod sursa (job #981540)
Cod sursa(job #981540)
#include <fstream>
#include <string.h>
#include <vector>
#define NMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[NMAX],B[NMAX];
int NXT[NMAX],NR;
vector<int> Q;
int LENA,LENB;
void read()
{
fin.getline(A,2000005);
fin.getline(B,2000005);
LENA=strlen(A);
LENB=strlen(B);
}
void next()
{
int k=-1,x;
for (x=1;x<=LENA;x++)
{
while (k>0 && A[k+1]!=A[x])
k=NXT[k];
if (A[k+1]==A[x])
k++;
NXT[x]=k;
}
}
void solve()
{
int i,x=-1;
next();
for (i=0;i<LENB;i++)
{
while (x>0 && A[x+1]!=B[i])
x=NXT[x];
if (A[x+1]==B[i])
x++;
if (x==LENA-1 && NR<1000)
{
Q.push_back(i-LENA+1);
NR++;
x=NXT[x];
}
}
fout<<NR<<'\n';
for (i=0;i<Q.size();i++)
fout<<Q[i]<<" ";
}
int main()
{
read();
solve();
fin.close();
fout.close();
return 0;
}