Imagine you want to implement a password policy.
You want to make sure that a user does not use a permutation of his previous password (case sensitive).
The first trivial thing we notice is that
- If one password is a permutation of the other then they have the same length.
We try to implement an efficient solution using xor.
We use the fact that x ^ x == 0.
The complexity is O(n) to figure out if character array a is a permutation of character array b.
As a reminder:
O(1) < O(lg n) < O(n) < O(n lg n) < O(n^2) < O(2^n) < O(n!)
If you would consider to sort the "string" and then to compare it then it would have
a complexitey of O(n log n) + O(n) = O((n log n) + n) = max(O(n log n) , O(n)) = O(n log n).
//returns 0 if a and b are permutations of each other, a value > 0 otherwise int is_perm(char *a , char *b) { int la = 0 ; int lb = 0 ; int i = 0 ; int check = 1 ; if(a == NULL || b == NULL) return(0) ; la = (int)strlen(a) ; lb = (int)strlen(b) ; if(la == 0 || lb == 0) return(0) ; if(la != lb) return(1) ; check = (a[0] ^ b[0]) ; for(i = 1 ; i < la ; i++) { check = (check ^ (a[i] ^ b[i])) ; } return(check) ; }How does it work?
Let's try an example by hand:
Let a = "das" and b = "sad" and c = "des"
das = 00100110 10000110 11001110
sad = 11001110 10000110 00100110
des = 00100110 10100110 11001110
Let's call is_perm(a , b)
count = 'd' ^ 's' = 00100110 ^ 11001110 = 11101000
count = (count ^ ('a' ^ 'a')) = 11101000 ^ 00000000 = 11101000
count = (count ^ ('s' ^ 'd')) = 11101000 ^ (11001110 ^ 00100110) = 00000000
count is 0, that means character array a is a permutation of character array b.
Let's call is_perm(a , c)
count = 'd' ^ 'd' = 00100110 ^ 00100110 = 00000000
count = (count ^ ('a' ^ 'e')) = 00000000 ^ (10000110 ^ 10100110)
= 00000000 ^ 00100000 = 00100000
count = (count ^ ('s' ^ 's')) = 00100000 ^ 00000000 = 00100000
count is 4, that means character array a is not a permutation of character array c.
Good luck in finding permutations.
You shares a lot of useful information about technology. Thank you for sharing this with us and keep sharing more like this.
ReplyDeleteC++ Training in Chennai
C C++ Training in Chennai
core java training in chennai
javascript training institute in chennai
javascript training in chennai
core java training in chennai
core java training
Thanks for the interesting blog that you have implemented here. Very helpful and innovative. Waiting for your next upcoming article.
ReplyDeleteJava Training in Chennai
Java Training Institute in Chennai
Java course in chennai
Java Training classes
Java Training
Java programming classes
core Java course
Nice post. Thanks for sharing! I want people to know just how good this information is in your article. It’s interesting content and Great work.
ReplyDeleteDigital Marketing Course In Kolkata
Thanks for this blog is very useful and unique
ReplyDelete7 tips to start a career in digital marketing
“Digital marketing is the marketing of product or service using digital technologies, mainly on the Internet, but also including mobile phones, display advertising, and any other digital medium”. This is the definition that you would get when you search for the term “Digital marketing” in google. Let’s give out a simpler explanation by saying, “the form of marketing, using the internet and technologies like phones, computer etc”
we have offered to the advanced syllabus course digital marketing for available join now
more details click the link now
[url]https://www.webdschool.com/digital-marketing-course-in-chennai.html [/url]
This information is meaningful and magnificent which you have shared here about the precedence and associativity of Java operators.
ReplyDeleteC and C++ Training Institute in chennai | C and C++ Training Institute in anna nagar | C and C++ Training Institute in omr | C and C++ Training Institute in porur | C and C++ Training Institute in tambaram | C and C++ Training Institute in velachery
It seems you are so busy in last month. The detail you shared about your work and it is really impressive that's why i am waiting for your post because i get the new ideas over here and you really write so well. good job
ReplyDeleteAi & Artificial Intelligence Course in Chennai
PHP Training in Chennai
Ethical Hacking Course in Chennai Blue Prism Training in Chennai
UiPath Training in Chennai
Kaliteli escort bayanlarla tanışma fırsatı yakalamak için tıkla: ankara escort - ankara escort - ankara escort - ankara escort - ankara escort - ankara escort - ankara escort - ankara escort - ankara escort
ReplyDeleteinstagram takipçi satın al - instagram takipçi satın al - tiktok takipçi satın al - instagram takipçi satın al - instagram beğeni satın al - instagram takipçi satın al - instagram takipçi satın al - instagram takipçi satın al - instagram takipçi satın al - binance güvenilir mi - binance güvenilir mi - binance güvenilir mi - binance güvenilir mi - instagram beğeni satın al - instagram beğeni satın al - polen filtresi - google haritalara yer ekleme - btcturk güvenilir mi - binance hesap açma - kuşadası kiralık villa - tiktok izlenme satın al - instagram takipçi satın al - sms onay - paribu sahibi - binance sahibi - btcturk sahibi - paribu ne zaman kuruldu - binance ne zaman kuruldu - btcturk ne zaman kuruldu - youtube izlenme satın al - torrent oyun - google haritalara yer ekleme - altyapısız internet - bedava internet - no deposit bonus forex - erkek spor ayakkabı - webturkey.net - minecraft premium hesap - karfiltre.com - tiktok jeton hilesi - tiktok beğeni satın al - microsoft word indir - misli indir
ReplyDeleteinstagram takipçi satın al
ReplyDeleteinstagram takipçi satın al
takipçi satın al
takipçi satın al
instagram takipçi satın al
takipçi satın al
instagram takipçi satın al
aşk kitapları
tiktok takipçi satın al
instagram beğeni satın al
youtube abone satın al
twitter takipçi satın al
tiktok beğeni satın al
tiktok izlenme satın al
twitter takipçi satın al
tiktok takipçi satın al
youtube abone satın al
tiktok beğeni satın al
instagram beğeni satın al
trend topic satın al
trend topic satın al
youtube abone satın al
beğeni satın al
tiktok izlenme satın al
sms onay
youtube izlenme satın al
tiktok beğeni satın al
sms onay
sms onay
perde modelleri
instagram takipçi satın al
takipçi satın al
tiktok jeton hilesi
pubg uc satın al
sultanbet
marsbahis
betboo
betboo
betboo
instagram takipçi satın al
ReplyDeleteucuz takipçi
takipçi satın al
https://takipcikenti.com
https://ucsatinal.org
instagram takipçi satın al
https://perdemodelleri.org
https://yazanadam.com
instagram takipçi satın al
balon perdeler
petek üstü perde
mutfak tül modelleri
kısa perde modelleri
fon perde modelleri
tül perde modelleri
https://atakanmedya.com
https://fatihmedya.com
https://smmpaketleri.com
https://takipcialdim.com
https://yazanadam.com
yasaklı sitelere giriş
aşk kitapları
yabancı şarkılar
sigorta sorgula
https://cozumlec.com
word indir ücretsiz
tiktok jeton hilesi
rastgele görüntülü sohbet
erkek spor ayakkabı
fitness moves
gym workouts
https://marsbahiscasino.org
http://4mcafee.com
http://paydayloansonlineare.com
ucuz takipçi
ReplyDeleteucuz takipçi
tiktok izlenme satın al
binance güvenilir mi
okex güvenilir mi
paribu güvenilir mi
bitexen güvenilir mi
coinbase güvenilir mi
seo fiyatları
ReplyDeletesaç ekimi
dedektör
instagram takipçi satın al
ankara evden eve nakliyat
fantezi iç giyim
sosyal medya yönetimi
mobil ödeme bozdurma
kripto para nasıl alınır
instagram beğeni satın al
ReplyDeleteyurtdışı kargo
seo fiyatları
saç ekimi
dedektör
fantazi iç giyim
sosyal medya yönetimi
farmasi üyelik
mobil ödeme bozdurma
bitcoin nasıl alınır
ReplyDeletetiktok jeton hilesi
youtube abone satın al
gate io güvenilir mi
referans kimliği nedir
tiktok takipçi satın al
bitcoin nasıl alınır
mobil ödeme bozdurma
mobil ödeme bozdurma
Form Pilot - form filler software. It designed for filling in paper forms (of any type) on your computer. It makes typewriters obsolete.Exif Editor Windows
ReplyDeleteCLO Standalone Crack helps you adjust the quality and range of each to make your 3D canvases smoother and more impressive. It has all the new and unique .Clo Standalone 7.0 228
ReplyDelete