8
\$\begingroup\$

Given two strings, a parent string and a query string respectively, your task is to determine how many times the query string, or an anagram of the query string; appears in the parent string, in a case-sensitive search.

Examples of Behaviour

Input 1

AdnBndAndBdaBn
dAn

Output 1

4

Explanation The substrings are highlighted in bold below:

AdnBndAndBdaBn

AdnBndAndBdaBn

AdnBndAndBdaBn

AdnBndAndBdaBn

Note the search MUST be case sensitive for all searches.

Input 2

AbrAcadAbRa
cAda

Output 2

2

This must work for standard ASCII only. This is code-golf, so shortest number of characters will get the tick of approval. Also please post a non-golfed version of your code along with the golfed version.

\$\endgroup\$
  • 2
    \$\begingroup\$ Important test case: abacacaba aac \$\endgroup\$ – Martin Ender May 15 '15 at 21:24
  • \$\begingroup\$ Will the parent string always be longer than the query string ? \$\endgroup\$ – Optimizer May 15 '15 at 22:52
  • \$\begingroup\$ Oh very good point! Yes @Optimizer, the parent string will always be longer than the query string. \$\endgroup\$ – WallyWest May 16 '15 at 0:52
  • \$\begingroup\$ @WallyWest What about the additional test case? Should overlapping occurrences of a single permutation be counted? \$\endgroup\$ – Martin Ender May 16 '15 at 3:15
  • 1
    \$\begingroup\$ Can you give a test case and its correct solution for your most recent comment? \$\endgroup\$ – isaacg May 16 '15 at 8:58
5
\$\begingroup\$

Pyth, 11 10 bytes

lfqSzST.:w

1 byte golf thanks to @Jakube.

Demonstration.

Takes the query string, followed by the parent string on a new line.

Ungolfed:

z = input()
len(filter(lambda T: sorted(z) == sorted(T), substrings(input())
\$\endgroup\$
  • \$\begingroup\$ 1 byte save, simply remove the last character of your solution ;-) \$\endgroup\$ – Jakube May 15 '15 at 23:19
  • \$\begingroup\$ @Jakube Oh, of course, that's wonderful. \$\endgroup\$ – isaacg May 16 '15 at 3:02
3
\$\begingroup\$

CJam, 13 bytes

le!lf{\/,(}:+

(12 bytes, if overlapping is allowed)

l$_,lew:$\e=

Input goes like:

dAn
AdnBndAndBdaBn

i.e.

<query string>
<parent string>

Thanks to Dennis for saving 3 bytes in the overlapping scenario

Try it online here

\$\endgroup\$
  • 1
    \$\begingroup\$ You can handle overlapping with the same byte count: ll1$,ew:$\$e= \$\endgroup\$ – Dennis May 16 '15 at 2:49
  • \$\begingroup\$ @Dennis That's really nice. 12 bytes : l$_,lew:$\e= But not sure if this would be valid now that OP has said that overlapping is not allowed. Let me see if I can reduce my current one. \$\endgroup\$ – Optimizer May 16 '15 at 8:26
2
\$\begingroup\$

JavaScript ES6, 95 bytes

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

This is a function that takes two arguments like this: f(parent,query).

It goes through all substrings of the parent string of the length of the query string and sorts them. If they are the same as the sorted query string, it increments n. Sorting string is annoying because it must be converted to an array, sorted, and converted back to a string. Ungolfed and testable code below.

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

\$\endgroup\$
2
\$\begingroup\$

Haskell, 77 68 bytes

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

Usage:

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

How it works: parent string is p, query string is s.

tails creates a list of it's parameter with successively removing the first element, e.g. tails "abcd" -> ["abcd","bcd","cd","d",""]. For every element x of this list take a 1 if the sorted first n elements (where n is the length of s) equal the sorted s. Sum the 1s.

Edit: tails instead of explicit recursion

\$\endgroup\$
2
\$\begingroup\$

Python, 61 bytes

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

This is a recursive algorithm. It checks whether the initial characters of the parent string, once sorted, are the same as the query string, sorted. Then, it recursive on the parent string with its first character removed. It terminates when the parent string is empty.

\$\endgroup\$
2
\$\begingroup\$

Python 2, 76 70 bytes

This lambda function iteratively compares each sorted substring with the target substring. The matches are counted and returned.

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

The ungolfed code:

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)

and the test output:

ba,abcba 2
dAn,AdnBndAndBdaBn 4
aac,abacacaba 2
\$\endgroup\$
  • \$\begingroup\$ ZOUNDS! I never saw that. I will edit and save some bytes. Thanks Jakube. \$\endgroup\$ – Logic Knight May 16 '15 at 10:32
2
\$\begingroup\$

Python 2, 124 118 bytes

Try it here

This is an anonymous lambda function. It can probably still be golfed further.

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

Ungolfed:

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
\$\endgroup\$
  • \$\begingroup\$ don't need re, you can just do string.count(substring) for each permutation \$\endgroup\$ – sirpercival May 15 '15 at 22:35
  • 2
    \$\begingroup\$ @sirpercival No, string.cound doesn't count overlapping occurrences, like in the f('aaa','aa'). \$\endgroup\$ – Jakube May 15 '15 at 23:13
  • \$\begingroup\$ ah, good call! i forgot about that. \$\endgroup\$ – sirpercival May 15 '15 at 23:20
  • 1
    \$\begingroup\$ import re,itertools as i saves 6 chars. (I haven't known before that it works.) \$\endgroup\$ – randomra May 15 '15 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.