Pagini recente » Cod sursa (job #3287750) | Cod sursa (job #1960912) | Cod sursa (job #1398526) | Cod sursa (job #2044024) | Cod sursa (job #2989415)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b; // modelul care se cauta, textul in care se cauta
int lp[2000001], s[1001], lm, i, ns; // lungimile prefixelor, solutiile
void kmp_table()
{int im=0, ip=0; // indice pentru model, indice pentru prefix
char c='\0';
lp[0]=-1; // !! ca sa se avanseze in text folosind formula [*]
while(im<=lm-1)
{if(a[im]==c)
{lp[im+1]=ip+1;
ip++;
im++;
}
else if(ip>0)ip=lp[ip];
else
{lp[im+1]=0;
im++;
}
c=a[ip];
}
}
void kmp_search()
{int it=0, im=0;
int lt=b.size(), lm=a.size();
while (it+im<=lt-1) // cat timp nu depasim ultimul caracter
{if(b[it+im]==a[im]) // Caracterele se potrivesc.
im++; // Trecem sa comparam urmatorul caracter.
else // Caracterele nu se potrivesc.
{it+=im-lp[im]; // noua pozitie in text [*]
if(im>0)im = lp[im]; // Mergem la primul loc unde nu am comparat.
}
if (im==lm) // S-au potrivit toate caracterele.
{ns++;
if(ns<=1000)
s[ns]=it;
}
}
}
int main()
{
fin>>a>>b;
lm=a.size();
kmp_table();
kmp_search();
fout<<ns<<"\n";
for(int i=1;i<=min(ns, 1000);i++)
fout<<s[i]<<" ";
return 0;
}