Зимни Математически Състезания 2005, Задача A2. ВИРУС
Условието на задачата може да прочетете
тук.
Решение
Ще предложа два начина за решаването на тази задача.
Единият се базира на алгоритъма за string matching на Кнут-Морис и Прат. С този
алгоритъм изкарах 60 точки на състезанието. Другият се базира на хеширане, или казано
иначе, на съпоставяне на стрингове и числа.
Първият
алгоритъм
лесно се реализира чрез използването на информацията, която ни дава алгоритъмът
на Кнут-Морис-Прат по време на изпълнението си, като ако не намери, че единият
стринг А се съдържа в другия B, то поне ни дава какъв максимален
префикс на А се съдържа в B. Използвайки тази информация можем да
намерим лесно отговора. Пробваме всеки суфикс на първия стринг, и намираме до
каква дължина максимално се среща във всеки друг стринг и от тези стойности
избираме минималната. Този алгоритъм има сложност О(N*L2).
Алгоритъм с
хеширане.
Първо на всеки стринг съпоставяме едно число. Това
можем да го направим по много начини, но този, който ще предложа е подходящ за
случая. Първата стъпка е на всеки символ от азбуката, която имаме, да
съпоставим число, това правим по следния начин – първият символ означаваме с 0, ..., последният с 15. Оттук надолу там, където в
аритметични операции използваме символ, всъщност използваме неговия целочислен
еквивалент. И така, ако имаме стринга А[]
с n елемента тогава можем да му
съпоставим следната стойност (хеш стойност):
A[1]*k(n-1)
+ A[2]*k(n-2) + ... + A[n-1]*k1 + A[n]*k0.
Kе някакво число и ще
наричаме това съпоставяне хеш функция от степен k. Ако стойностите на А[1..n] са в интервала 0..l-1, където l<=k тогава на различен стринг с дължина n ще се съпостави различно число. Но понеже не можем да пазим
такива големи числа, пазим стойностите на хеш-функци по модул някакво число,
което е достатъчно малко. Но така пък може да се случи така че два различни
стринга имат едни и същои стойности (за това по-късно).
Сега обратно към задачата. Да
предположим, че
искаме да решим следната задача: съществува ли стринг с дължина l, който е подстринг на всички дадени стрингове.
Тази задача се разделя на две подзадачи. Първо намираме хеш функцията на всеки
подстринг с желаната дължина. После проверяваме дали има такава стойност, която
се среща във всичките стрингове. Ако има такава (или такива) трябва да проверим
дали наистина съвпадат самите подстрингове или само хеш-стойността им. Ако открием
съвпадение, намираме и отговора на задачата.
1) Първа част - Хеширането или
изчисляването на хеш стойностите. Да вземем един стринг A[n] и искаме да сметнем какви са хеш стойностите от степен k на всички подстрингове с дължина l. Можем да за всеки да сметнем
стойността по горната формула, но това би било твърде бавно. За стринга А[1..l] вече показах как може да се
сметне със линейна сложност. Сега обаче искаме за всеки от стринговете А[2..l+1], A[3..l+2] ... A[n-l-2..n-1],
A[n-l-1..n] пресметнем тази стойност с
константна сложност. Ето как става това. Важно е да се отбележи че когато
всички сметки се извършват по модул (както е в случая), можем да използваме
само операциите *-+, като са спазени следните равенства:
a+b)%c =
(a%c+b%c)%c,
(a-b)%c = (a%c-b%c)%c,
(a*b)%c =
((a%c)*(b%c))%c.
Следователно няма проблем да пазим междинните
стойности по модул. Тогава можем свободно да извършаме тези операции със
стойности по модул, все едно не са по модул. И така: C[i] ще наричаме хеш стойността на стринга с дължина l завършващ в А[i]. В сила са следните
равенства:
C[i]=A[i-l+1]*k(l-1)
+ A[i-l+2]*k(l-2) + ... + A[i-1]*k1 + A[i]*1 = A[i-l+1]*k(l-1)
+ M, където
М очевидно е равно на A[i-l+2]*k(l-2) +
... + A[i-1]*k1 + A[i]*1 = C[i] - A[i-l+1]*k(l-1).
C[i+1]=A[i-l+2]*k(l-1)
+ A[i-l+3]*k(l-2) + ... + A[i]*k1 + A[i+1]*1
= ( A[i-l+2]*k(l-2)
+ A[i-l+3]*k(l-3) + ... + A[i]*1 )*k + A[i+1]*1 = M*k + A[i+1]
= ( C[i] -
A[i-l+1]*k(l-1) )*k +A[i+1]
Сега ще покажа как ако знаем C[i] как ще пресметнем с константна сложност C[i+1].
C[i+1]=( C[i]
- A[i-l+1]*k(l-1) )*k +A[i+1]. Числата
C[i], k,
A[i+1] са известни. Остава да намерим
начим да пресметнем A[i-l+1]*k(l-1)
бързо и тогава можем без проблем да намерим C[i+1],
използвайки свойствата на операциите по модул. Знаем A[i-l+1] и k. Можем да
преизчислим един масив power[], който
да ни казва стойността на k повдинато
в която ни трябва степен (естествено резултатът се пази отново по модул). Така
изчислихме C[i+1]. Следователно можем
да сметнем всички стойности C[j] j=l..n
и това можем да го направим за всеки стринг. нека отсега нататък C(i,j) да означава стойността на хеш
функцията на подстринга с дължина l в
стринга i, завършащ в j-ти елемент.
2) Втора част - намиране на еднакви хеш
стойности във всеки стринг и проверката дали наистина съвпадат съответните
стрингове или не.
2.1) Първата част: да намерим
кои стойности се срещат във всеки стринг. Това можем да направим чрез следния
алгоритъм. Нека имаме масив S[] с
големина равна на модула, по който извършваме всички изчисления. За всеки
стринг i правим следното: обхождаме
краищата j на всички негови
подстрингове с дължина l и гледаме в
този масив S в колко стринга досега
сме срещали стойността C(i,j). Ako тя
е равна на i тогава не променяме
нищо, тъй като тази стойност се е срещала във всички стрингове
досега(включително и сегашния). Ако е равна на i-1, това значи, че тя се е срещала във всички стрингове досега
(без текущия). Но тъй като сме я намерили в текущия, тогава променяме
стойността на S[C(i,j)] = i. Ако пък е по-малка от i-1 тогава тя не се е срещала поне в предпоследния стринг,
следователно не може да се среща във всички.
2.2)
Сега втората част. Искаме подходяща структура от данни и подходящ
алгоритъм с които да правим следната операция: Търсим в даден стринг
на кои позиции завършва стринг с хеш стойности
равни на дадено число. Да предположим, че имаме такава структура ( по-късно
ще обясня каква точно ще използваме). Обхождаме всички подстрингове (с край j) и с
дължина l в първия стринг. Обхождаме всички подстрингове (с край j) и с
дължина l в първия стринг. Ако стойността на S[C(1,j)] е
равна на броя на стринговете това означава, че и в другите стрингове има
подстрингове със същата хеш стойност. Затова трябва да проверим дали наистина
съвпадат. Да предположим че тази стойност е F.
И ето тук възниква въпросът да намерим позициите, в които завършват
подстрингове с хеш стойност F в
стринговете 2,3,4,5....
Като
намерим отговора на този въпрос остава да проверим дали някой
от тези подстрингове наистина съвпада с търсения. Проверката се извършва
елементарно, чрез сравняване на елементите им, като ако стигнем до различие,
веднага прекратяваме и ги обявяваме за различни. Също така ако открием че
даден подстринг се среща в някой стринг пак прекратяваме търсенето в този стринг.
И отново, ако намерим, че даден подстринг на първия стринг се среща във
всички други стрингове, то няма смисъл да търсим повече, тъй като сме си отговорили на задачата.
Сега да обясния каква структура ще използваме за
споменатото търсене. Аз лично съм сложил в един масив всички позиции във всички
стрингове, които са краища на подстрингове с дължина l. Слагам в масива тройки от вида (стринг, хеш стойност, позиция на
тази хеш-стойност). Сортирането на масива (като за критерий ми служат първите
два елемента) ми позволява да правя двоично търсене и по такъв начин намирам
индекса в масива където е първия (защото може да има и няколко) елемент, който
отговаря на въпроса ни: "да намерим позициите, в
които завършват подстрингове с хеш стойност F в стринговете 2,3,4,5....". Но това не е най-доброто решение. Теоретично по-добри
резултати биха се получили ако се използва отново хеш-функция, но на практика
няма смисъл, а и е излишен код.
Сега вече можем да решим задачата: "искаме да
решим следната задача: съществува ли стринг с дължина l, който е подстринг на
всички дадени стрингове". Но това не дава отговор на задачата ВИРУС. Търсим най-дългия такъв стринг. Нека предположим че знаем,
че съществува подстринг с дължина m, който се среща във всички стрингове.
Тогава знаем, че отговорът е минимум m. Ако пък знаем, че няма такъв постринг,
тогава отговорът задължително е по-малък
от m. Това ни позволява да използваме двоично търсене за намиране на дължината
на най-дългия общ подстринг, каквото се търси и във Вирус.
Забележки:
1) Първо трябва изберем
подходяща стойност на k. По принцип
когато се правят хеш-фукции е добре да се избират прости числа. Теоретично не
би трябвало да има значение каква е стойността, но аз избрах да е по голяма от 16 и да е просто число (17,
19, 23) вършат работа, но тествах и
с трите дава пак същите резултати.
2) Трябва да изберем подходяща
стойност за mod. Това е модула по
който извършваме всички сметки. Той трябва
да е голямо просто число. Първоначално бях избрал 219-1 но после го смених на 219-400001 и вече работеше много по бързо. По принцип колкото е по голяма тази
стойност толкова по трудно ще срещнем два стринга с еднакви хеш стойнсти, но
различни. От друга страна колкото е по малка, толкова по малък ще е масива S[], за който говорих в 2.1). Тествах и поне при моята
реализация, компромисната стойнст е от порядъка на 100 000.
3) Сложността на програмата ми
е трудна за оценка но е минимум O(logL*N*L)
което е само пресмятането на нещата казани в 2.1). Но тестовете (не само на журито, а и много други) показват,
че действията в 2.2) почти не забавят
програмата. Това се дължи на факта, че има много малко лъжливи съвпадения.
4) В началото сортирам
стринговете по дължина като се надявам най-късият стринг като е първи да
увеличи бързодействието на програмата, но това на практика не става, или поне
не и в тестовете, с които я тествах.
5) Не правя точно двоично
търсене за да открия най-дългия подстринг. Ако знам, че отговорът е в интервала
[a,b] тогава аз вместо да проверя
средния елемент (a+b)/2 аз търся малко по надясно в
(a+b*2)/3. Така се увеличава вероятността да попадна на дължина която
не е валидна, а това по бързо се открива, отколкотоако има подстринг с такава дължина.
Sкоростта на програмата се
уеличава с около 20%.
Примерна реализация:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#define in stdin;
#define mx 65536 // max length
#define maxx 32 // max strings
#define pr 23 // small prime
#define mod 124287 // large prime
#define MOD(a) ((a%mod+mod)%mod)
FILE*fn;
FILE*fn1;
int powpr[mx];
int end;
//////////////////// end consts & best
char ss[maxx][mx];
int c;
int ll[mx];
int sortt(void)
{int q1,q2,c1,c2;
for(q2=0;q2<c;q2++)for(q1=q2+1;q1<c;q1++)if(ll[q1]<ll[q2])
{strcpy(ss[mx-1],ss[q1]);
strcpy(ss[q1],ss[q2]);
strcpy(ss[q2],ss[mx-1]);
c1=ll[q1];
ll[q1]=ll[q2];
ll[q2]=c1;}
ss[mx-1][0]=0;
return 0;}
int replace(void)
{int q1,q2;
for(q1=0;q1<c;q1++)for(q2=0;q2<ll[q1];q2++)
if(ss[q1][q2]<'A')ss[q1][q2]=ss[q1][q2]-'0'+'G';
return 0;}
int restore(void)
{int q1,q2;
for(q1=0;q1<c;q1++)for(q2=0;q2<ll[q1];q2++)
if(ss[q1][q2]>'F')ss[q1][q2]=ss[q1][q2]-'G'+'0';
return 0;}
/////////////////////// end storage
int calcpowpr(void)
{int q1;
powpr[0]=1;
for(q1=1;q1<mx;q1++)powpr[q1]=(powpr[q1-1]*pr)%mod;
return 0;}
int init(void)
{int q1;
fn=in;
fscanf(fn,"%d\n",&c);
for(q1=0;q1<c;q1++)fgets(ss[q1],mx,fn);
for(q1=0;q1<c;q1++)ll[q1]=strlen(ss[q1]);
for(q1=0;q1<c;q1++){ss[q1][ll[q1]-1]=0;ll[q1]--;}
fclose(fn);
sortt();
replace();
calcpowpr();
return 0;}
/////////////////////// end initialization
int h[maxx][mx];
int hash(int len)
{int q1,q2,c1,c2,c3;
for(q1=0;q1<c;q1++)
{for(q2=0;q2<len-1;q2++)h[q1][q2]=-1;
c1=0;
for(q2=0;q2<len;q2++)
{c1=c1*pr+ss[q1][q2]-'A';
c1=MOD(c1);}
h[q1][len-1]=c1;
for(q2=len;q2<ll[q1];q2++)
{c1-=powpr[len-1]*(ss[q1][q2-len]-'A');
c1=MOD(c1);
c1*=pr;
c1+=ss[q1][q2]-'A';
c1=MOD(c1);
h[q1][q2]=c1;}}
return 0;}
/////////////////////// end hash
typedef struct {short where;int place,which;}rec;
int bbb1;
int cmp(const void*aa,const void*bb)
{rec*a,*b;
a=(rec*)aa;
bbb1++;
b=(rec*)bb;
if(a->where>b->where)return 1;
if(a->where==b->where) if(a->which>b->which)return 1;
if(a->where==b->where)if(a->which==b->which)return 0;
return -1;}
int bs(rec*a,rec*b,int right)
{int l,m,r,c1;
l=0;r=right;
while(l!=r)
{m=(l+r)/2;
c1=cmp(a,b+m);
if(c1==0)r=m;
else if(c1==1)l=m+1;
else r=m;}
return l;}
////////////////////// end rec manipulations
rec s[mx*maxx/4];
rec e1;
int sc;
int iff[mod];
int calculate(int len)
{int q1,q2;
for(q1=0;q1<mod;q1++)iff[q1]=0;
for(q1=0;q1<c;q1++)for(q2=len-1;q2<ll[q1];q2++)
if(iff[h[q1][q2]]==q1)
iff[h[q1][q2]]++;
for(q1=0;q1<mod;q1++)if(iff[q1]==c)iff[q1]=1;else iff[q1]=0;
sc=0;
for(q1=0;q1<c;q1++)for(q2=len-1;q2<ll[q1];q2++)if(iff[h[q1][q2]])
{e1.where=q1;
e1.place=q2;
e1.which=h[q1][q2];
s[sc++]=e1;}
// fprintf(fn1,"%d %d\n",sc,len);
qsort(s,sc,sizeof(s[0]),cmp);
return 0;}
/////////////////////// end calculate
int check(int s1,int s2,int p1,int p2,int len)
{int q1;
for(q1=0;q1<len;q1++)
if(ss[s1][p1-q1]!=ss[s2][p2-q1])break;
if(q1==len)return 1;
return 0;}
/////////////////////// end check
int doit(int len)
{int q1,q2,q3,c1,c2,c3;
rec e1;
hash(len);
calculate(len);
if(sc==0)return 0;
for(q1=len-1;q1<ll[0];q1++)if(iff[h[0][q1]])
{
for(q2=1;q2<c;q2++)
{e1.where=q2;
e1.which=h[0][q1];
c1=bs(&e1,s,sc-1);
c2=c1;
c3=0;
while(c2<sc&&s[c2].where==s[c1].where&&s[c2].which==s[c1].which)
{c3=check(0,q2,q1,s[c2].place,len);
if(c3)break;
c2++;}
if(c3)continue;
if(!c3)break;}
if(q2==c)break;}
if(q1!=ll[0]){end=q1;return 1;}
return 0;}
/////////////////////// end doit
/////////////////// start main
int l,r,m,q1,c1;
int main()
{clock();
init();
l=ll[0]/10;
r=ll[0]/2+2;
if(r>ll[0])r=ll[0];
if(l<1)l=1;
while(l!=r)
{m=(l+2*r+1)/3;
c1=doit(m);
if(c1==0)r=m-1;
else if(c1==1)l=m;}
doit(l);
restore();
ss[0][end+1]=0;
printf("%s\n",ss[0]+end-l+1);//;q1<=end;q1++)printf("%c",ss[0][q1]);
return 0;}
Автор: Светослав Колев
обратно към брой 27
|