Pagini recente » Cod sursa (job #2601710) | Cod sursa (job #2986215) | Cod sursa (job #60327) | Cod sursa (job #475210) | Cod sursa (job #1812388)
/*
Problema se bazeaza pe aceeasi idee ca Potrivirea Sirurilor de pe infoarena
doar ca returneaza pozitia primului caracter din prima subsecventa a sirului a.
In caz de nu apare , se va afisa pozitia n, prima de dupa ultimul caracter al sirului a.
Indexarea incepe de pe 0
*/
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int ct=0,rez[1003];
unsigned int q = 65521; /* numarul prim < 2^16 */
unsigned int d = 257; /* baza pentru interpretarea numerica a stringului */
unsigned int dM; /* d^(M-1), unde M este lungimea modelului */
void hash_init(int M) {
dM = 1;
for (int i = 1; i < M; i++) dM = (dM * d) % q ;
}
unsigned int hash(char* t, int n){
unsigned h = t[0];
for (int i = 1; i < n; i++)
h = (d * h + t[i]) % q;
return h;
}
unsigned int hash_next(char* t, int M, int h){
unsigned int oldest = (dM * t[0]) % q;
unsigned int oldest_removed = ( (h + q) - oldest ) % q;
return (d * oldest_removed + t[M]) % q;
}
int equal_string(char* p, char* q, int n){
/* returneaza true daca primele n caractere ale lui p si q sunt identice */
return n == 0 || ( *p == *q && equal_string(p + 1, q + 1, n - 1) );
}
void rksearch(char* p, char* a)
/*
returneaza indicele primei aparitii a sirului p in a.
returneaza lungimea sirului a daca sirul p nu apare in sirul a.
*/
{
int M = strlen(p);
int N = strlen(a);
hash_init(M);
unsigned int h1 = hash(p, M);
unsigned int h2 = hash(a, M);
for (char* b = a; b < a + N - M; b++)
{
if (h2 == h1 && equal_string(p, b, M)) rez[++ct]=b-a;
h2 = hash_next(b, M, h2);
}
}
int main()
{
char *p; p=new char(2000);
fin>>p;
char *a; a=new char(2000);
fin>>a;
//fout<<p<<" "<<a<<"\n";
rksearch(p,a);
fout<<ct<<"\n";
for(int i=1; i<=ct; ++i)
fout<<rez[i]<<" ";
return 0;
}