Pagini recente » Istoria paginii runda/qwe/clasament | Cod sursa (job #1288215) | Cod sursa (job #1347433) | Cod sursa (job #1769824) | Cod sursa (job #1808111)
#include<iostream>
#include<fstream>
#include<vector>
#define NMax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int N,M,nrp;
char A[NMax],B[NMax];
int pi[NMax];
vector <int> Sol;
void Read()
{
fin.getline(A+1,NMax);
fin.getline(B+1,NMax);
while(A[++N]); N--;
while(B[++M]); M--;
}
void Precalculate()
{
pi[1] = 0;
for (int i = 2 ; i <= N ; ++i)
{
while (nrp && A[nrp+1] != A[i])
nrp = pi[nrp];
if (A[nrp+1] == A[i])
nrp++;
pi[i] = nrp;
}
}
void KMP()
{
nrp = 0;
for (int i = 1; i <= M; ++i)
{
while (nrp && A[nrp+1] != B[i])
nrp = pi[nrp];
if (A[nrp+1] == B[i])
nrp++;
if (nrp == N)
{
nrp = pi[N];
if (Sol.size() < 1000)
Sol.push_back(i-N);
}
}
}
void Print()
{
fout<<Sol.size()<<"\n";
for(int i = 0 ; i < Sol.size() ; ++i)
fout<<Sol[i]<<" ";
fout<<"\n";
}
int main()
{
Read();
Precalculate();
KMP();
Print();
fin.close();
fout.close();
return 0;
}