Pagini recente » Cod sursa (job #2602741) | Cod sursa (job #1174731) | Cod sursa (job #1926168) | Cod sursa (job #1850151) | Cod sursa (job #777304)
Cod sursa(job #777304)
// Algoritmul KMP are complexitatea liniara O(N+M) si ajuta
// la potrivirea unui sir peste altul. Pentru a afla locul
// potrivirilor putem face sirul de prefixe ale primului sir.
// Sirul de prefixe consta in aflarea la trimiterea de la sfarsitul
// sirului A pe pozitia de unde am putea continua algoritmul.
// Viteza cu care se face sirul de prefixe este relativ mare
// deoarece o siftare spre stanga se produce in maxim 2 pasi.
// Exemplu:
// A= ABABBABBA
// S= 001201201 // sir de prefixe
// Siftarea spre stanga se face cu ajutorul variabilei q:
// variabila q creste nu creste pana cand nu se gaseste un cracter
// identic cu primul, apoi q creste daca A[q]=A[i] , iar daca
// A[q]!=A[i] atunci il siftam pe q la stanga.
// Dupa finalul parcurgerii sunt necesare doar elementele
// din vectorul de prefixe.
#include <fstream>
#include <cstring>
using namespace std;
const int Nmax = 2000011;
char A[Nmax],B[Nmax];
int N,M,Sift[Nmax];
int Q[1011],Con;
ofstream G("strmatch.out");
void Make_sift()
{
int q=0;
for (int i=2;i<=N;++i )
{
while ( q && A[i]!=A[q+1] ) q = Sift[q];
if ( A[i]==A[q+1] ) ++q;
Sift[i] = q;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
gets(A); N=strlen( A );
gets(B); M=strlen( B );
for (int i=N;i;--i) A[i]=A[i-1];
for (int i=M;i;--i) B[i]=B[i-1];
A[0]=B[0]=0;
Make_sift();
if ( N>M ) G<<"0\n";
int q=0;
for (int i=1;i<=M;++i)
{
while ( q && B[i]!=A[q+1] ) q = Sift[q];
if ( B[i]==A[q+1] ) ++q;
if ( q==N )
{
++Con;
if ( Con <= 1000 )
Q[Con]=i-N;
q = Sift[q];
}
}
G<<Con<<'\n';
for (int i=1;i<=min(Con,1000);++i)
G<<Q[i]<<' ';
G<<'\n';
}