Detecting anagrams within a Parent String

Question

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.

Answer 1

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())

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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