Pagini recente » Cod sursa (job #919121) | Cod sursa (job #1820792) | Cod sursa (job #1094934) | Cod sursa (job #955758) | Cod sursa (job #2104206)
#include<fstream>
#include<string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMax=2000005;
int Poz[NMax],N,M,Sol[1003],Dim=0;
string Pattern,Text;
void PreKMP()
{
int K=0;
for(int i=2;i<N;i++)
{
while(K && Pattern[i]!=Pattern[K+1])
K=Poz[K];
if(Pattern[i]==Pattern[K+1])
K++;
Poz[i]=K;
}
}
void KMP()
{
PreKMP();
int K=0;
for(int i=1;i<M;i++)
{
while(K && Text[i]!=Pattern[K+1])
K=Poz[K];
if(Text[i]==Pattern[K+1])
K++;
if(K==N-1)
{
K=Poz[K];
Dim++;
if(Dim<=1000)
Sol[Dim]=i-N+1;
}
}
}
int main()
{
fin>>Pattern>>Text;
Pattern=' '+Pattern;
Text=' '+Text;
N=Pattern.size();
M=Text.size();
KMP();
fout<<Dim<<'\n';
Dim=min(Dim,1000);
for(int i=1;i<=Dim;i++)
fout<<Sol[i]<<" ";
}