Pagini recente » Cod sursa (job #951215) | Cod sursa (job #1068533) | Cod sursa (job #1523920) | Cod sursa (job #3037759) | Cod sursa (job #814857)
Cod sursa(job #814857)
#include <stdio.h>
#include <string.h>
#include <vector>
#define MOD1 100007
#define MOD2 100021
#define BASE 123
#define Lmax 2000003
using namespace std;
char A[Lmax], B[Lmax];
vector<int> sol;
void read_data()
{
FILE*f = fopen("strmatch.in","r");
fscanf(f,"%s %s",A,B);
fclose(f);
}
int main()
{
read_data();
int i,hash_a1=0,hash_a2=0,a_size,b_size,hash1=0,hash2=0,P1=1,P2=1;
a_size = strlen(A);
b_size = strlen(B);
for(i=0;i<a_size;++i)//calculez cheile pt primele caractere din a si din b(primele a_size caracter)
{
hash_a1 = (hash_a1*BASE + A[i])%MOD1;
hash_a2 = (hash_a2*BASE + A[i])%MOD2;
hash1 = (hash1 * BASE + B[i])%MOD1;
hash2 = (hash2 * BASE + B[i])%MOD2;
if(i!=0)//ne trebuie pow(base,a_size-1) pt ca tot timpul vom scadea primul element care este de forma v[0]*pow(base,a_size-1);
{
P1 = (P1*BASE)%MOD1;
P2 = (P2*BASE)%MOD2;
}
}
if(hash1 == hash_a1 && hash2 == hash_a2)//daca primele a_size elemente coincid avem o solutie
sol.push_back(0);
for(i=a_size;i<b_size;++i)
{
//scadem din cheie elementul care a ramas pe dinafara dupa care inmultim cu base ca sa refacem puterile si adunam noul element
hash1 = (((hash1 - B[i-a_size]*P1)%MOD1 + MOD1)*BASE + B[i])%MOD1;
hash2 = (((hash2 - B[i-a_size]*P2)%MOD2 + MOD2)*BASE + B[i])%MOD2;
if(hash1 == hash_a1 && hash2 == hash_a2)//daca am solutie o salvez
sol.push_back(i-a_size+1);
}
FILE*g = fopen("strmatch.out","w");
fprintf(g,"%d\n",sol.size());
i=0;
for(vector<int>::iterator it = sol.begin();it!=sol.end() && i<1000;++it,++i)
fprintf(g,"%d ",*it);
fclose(g);
return 0;
}