Pagini recente » Cod sursa (job #2592263) | Cod sursa (job #2192251) | Cod sursa (job #1421341) | Cod sursa (job #1801484) | Cod sursa (job #777300)
Cod sursa(job #777300)
// 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 <queue>
#include <cstring>
using namespace std;
const int Nmax = 20000011;
char A[Nmax],B[Nmax];
int N,M,Sift[Nmax],Con;
queue< int > Q;
ifstream F("strmatch.in");
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()
{
F.getline(A,Nmax,'\n'); N=strlen( A );
F.getline(B,Nmax,'\n'); 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 ( int( Q.size() ) < 1000 )
Q.push( i-N );
q = Sift[q];
}
}
G<<Con<<'\n';
while ( int(Q.size()) > 1 )
{
G<<Q.front()<<' ';
Q.pop();
}
G<<Q.front()<<'\n';
}