Mendeteksi anagram dalam Parent String

9

Diberikan dua string, string induk dan string kueri masing-masing, tugas Anda adalah menentukan berapa kali string kueri, atau anagram string kueri ; muncul di string induk, dalam pencarian case-sensitive.

Contoh Perilaku

Input 1

AdnBndAndBdaBn
dAn

Output 1

4

Penjelasan Substring disorot dalam huruf tebal di bawah ini:

Adn BndAndBdaBn

AdnB ndA ndBdaBn

AdnBn dAn dBdaBn

AdnBnd Dan BdaBn

Perhatikan bahwa pencarian HARUS peka terhadap semua pencarian.

Input 2

AbrAcadAbRa
cAda

Keluaran 2

2

Ini harus bekerja hanya untuk ASCII standar. Ini adalah kode-golf, sehingga jumlah karakter terpendek akan mendapat tanda centang persetujuan. Silakan juga memposting versi non-golf kode Anda bersama dengan versi golf.

WallyWest
sumber
2
Kasus uji penting:abacacaba aac
Martin Ender
Apakah string induk selalu lebih panjang dari string kueri?
Pengoptimal
Oh, bagus sekali! Ya @ Opptizer, string induk akan selalu lebih panjang dari string kueri.
WallyWest
@WallyWest Bagaimana dengan test case tambahan? Haruskah tumpang tindih kejadian permutasi tunggal dihitung?
Martin Ender
1
Bisakah Anda memberikan test case dan solusi yang tepat untuk komentar terakhir Anda?
isaacg

Jawaban:

5

Pyth, 11 10 byte

lfqSzST.:w

1 byte golf berkat @Jakube.

Demonstrasi.

Mengambil string kueri, diikuti oleh string induk pada baris baru.

Tidak Disatukan:

z = input()
len(filter(lambda T: sorted(z) == sorted(T), substrings(input())
isaacg
sumber
Hemat 1 byte, cukup hapus karakter terakhir dari solusi Anda ;-)
Jakube
@ Jakube Oh, tentu saja, itu luar biasa.
isaacg
3

CJam, 13 byte

le!lf{\/,(}:+

(12 byte, jika tumpang tindih diizinkan)

l$_,lew:$\e=

Masukan seperti:

dAn
AdnBndAndBdaBn

yaitu

<query string>
<parent string>

Terima kasih kepada Dennis karena telah menyimpan 3 byte dalam skenario yang tumpang tindih

Cobalah online di sini

Pengoptimal
sumber
1
Anda dapat menangani tumpang tindih dengan jumlah byte yang sama:ll1$,ew:$\$e=
Dennis
@ Dennis Itu sangat bagus. 12 byte: l$_,lew:$\e=Tetapi tidak yakin apakah ini akan valid sekarang karena OP telah mengatakan bahwa tumpang tindih tidak diperbolehkan. Biarkan saya melihat apakah saya dapat mengurangi yang sekarang.
Pengoptimal
2

JavaScript ES6, 95 byte

f=(p,q,n=0,s=a=>[...a].sort().join(''))=>[...p].map((_,i)=>n+=s(p.substr(i,q.length))==s(q))&&n

Ini adalah fungsi yang membutuhkan dua argumen seperti ini: f(parent,query).

Itu melewati semua substring dari string induk dari panjang string kueri dan mengurutkannya. Jika mereka sama dengan string kueri yang diurutkan, maka akan bertambah n. Mengurutkan string menjengkelkan karena harus dikonversi ke array, diurutkan, dan dikonversi kembali ke string. Kode tidak diuji dan diuji di bawah ini.

var f = function(p, q) {
  var n = 0
  var s = function(a) {
    return a.split('').sort().join('')
  }
  
  p.split('').map(function(_, i) {
    n += s(p.substr(i, q.length)) == s(q)
  })
  return n
}

// testing code below
document.getElementById('go').onclick = function() {
  var parent = document.getElementById('parent').value,
    query = document.getElementById('query').value;
  document.getElementById('output').innerHTML = f(parent, query);
}
<label>Parent: <input id="parent" value="AdnBndAndBdaBn"/></label><br />
<label>Query:  <input id="query" value="dAn"/></label><br />
<button id="go">Go</button><br />
<samp id="output">&mdash;</samp> anagrams found

NinjaBearMonkey
sumber
2

Haskell, 77 68 byte

import Data.List
p#s=sum[1|x<-tails p,sort s==sort(take(length s)x)]

Pemakaian:

*Main> "AdnBndAndBdaBn" # "dAn"
4
*Main> "AbrAcadAbRa" # "cAda"
2
*Main> "abacacaba"# "aac"
2

Cara kerjanya: string induk adalah p, string kueri s.

tailsmembuat daftar parameternya dengan menghapus elemen pertama, misalnya tails "abcd" -> ["abcd","bcd","cd","d",""]. Untuk setiap elemen xdaftar ini, ambil 1jika nelemen yang diurutkan pertama (di mana npanjangnya s) sama dengan yang diurutkan s. Jumlahkan 1s.

Sunting: tailsalih-alih rekursi eksplisit

nimi
sumber
2

Python, 61 byte

s=sorted
f=lambda a,b:a>''and(s(b)==s(a[:len(b)]))+f(a[1:],b)

Ini adalah algoritma rekursif. Ia memeriksa apakah karakter awal dari string induk, setelah diurutkan, sama dengan string kueri, diurutkan. Kemudian, itu rekursif pada string induk dengan karakter pertamanya dihapus. Ini berakhir ketika string induk kosong.

isaacg
sumber
2

Python 2, 76 70 byte

Fungsi lambda ini secara iteratif membandingkan setiap substring yang diurutkan dengan substring target. Pertandingan dihitung dan dikembalikan.

lambda a,d:sum(sorted(d[n:n+len(a)])==sorted(a)for n in range(len(d)))

Kode yang tidak dipisahkan:

f = lambda substr, text: sum(
    sorted(text[n:n+len(substr)]) == sorted(substr)
    for n in range(len(text))
    )

def test(tests):
    for t in tests.split():
        substr, text  = t.split(',')
        print t, f(substr, text)

tests = '''ba,abcba dAn,AdnBndAndBdaBn aac,abacacaba'''
test(tests)

dan hasil tes:

ba,abcba 2
dAn,AdnBndAndBdaBn 4
aac,abacacaba 2
Ksatria Logika
sumber
ZOUNDS! Saya tidak pernah melihatnya. Saya akan mengedit dan menyimpan beberapa byte. Terima kasih Jakube.
Logic Knight
2

Python 2, 124 118 byte

Coba di sini

Ini adalah fungsi lambda anonim. Mungkin masih bisa bermain golf lebih lanjut.

import re,itertools as i
lambda p,q:sum(len(re.findall('(?='+''.join(i)+')',p))for i in set(i.permutations(q,len(q))))

Tidak Disatukan:

from itertools import*
import re
def f(p,q):
    c=0
    for i in set(permutations(q,len(q))):
        c+=len(re.findall('(?='+''.join(i)+')',p))
    print c
mbomb007
sumber
tidak perlu kembali, Anda cukup melakukan string.count (substring) untuk setiap permutasi
sirpercival
2
@sirpercival Tidak, string.cound tidak menghitung kejadian yang tumpang tindih, seperti di f('aaa','aa').
Jakube
ah, panggilan yang bagus! saya lupa tentang itu.
sirpercival
1
import re,itertools as imenghemat 6 karakter. (Saya belum tahu sebelumnya bahwa itu bekerja.)
randomra