Pagini recente » Cod sursa (job #2720913) | Cod sursa (job #255134) | Cod sursa (job #279103) | Cod sursa (job #3134431) | Cod sursa (job #1829283)
/*KMP
*/
#include <fstream>
#include <vector>
#include <cstring>
using namespace std ;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
char A[(int)(2e6+2)] , B[(int)(2e6+2)]; //memoreaza cele 2 siruri
int precomputing[(int)(2e6+2)] , M , N ; //memoreaza sirul prefixurilor si lungimile sirurilor citite
vector <int> Sol;//vectorul solutie
void prefix_computing()
{
int poz = 2 ;//pt. unde calculam precomputing[poz]- denota pozitia curenta pt care calculam
int cnd = 0 ;//desemneaza urmatorul caracter a subisurului candidat curent
precomputing[0] = -1 , precomputing[1] = 0; //valori initiale
while ( poz < M )
{
if ( A[poz-1] == A[cnd] ) //daca substringul continua
precomputing[poz++] = ++cnd;
else if ( cnd > 0 ) //daca substringul nu continua dar "avem unde sa ne intoarcem"
cnd = precomputing[cnd] ;
else // nu mai avem nici de intors ( lipsa de candidati ) adica cnd = 0
precomputing[poz++] = 0;
}
}
void KMP_search()
{
int i = 0;//pozitia curenta in A
int j = 0;//pozitia curenta in B
while ( i + j < N ) //cat timp avem sanse de un subsir care sa fie chiar pana in capat ( ultima varianta)
{
if ( A[i] == B[j + i] )
{
if ( i == M - 1 )
{
if ( Sol.size() < 1000 )
Sol.push_back(j) ;
j = j + i - precomputing[i] , i = precomputing[i] ;
}
else
++i ;
}
else if ( precomputing[i] >= 0 )
j = j + i - precomputing[i] , i = precomputing[i] ;
else
++j , i = 0;
}
}
int main ()
{
f.getline ( A , 2e6+1 );
M = strlen(A) ;
f.getline ( B , 2e6+1 );
N = strlen(B) ;
prefix_computing();
KMP_search();
g << Sol.size() << "\n" ;
for ( const int & x : Sol )
g << x << " ";
}