## Count All Matches

### March 10, 2015

This is simple if you think recursively:

```(define (count-all-matches needle haystack)   (let loop ((needle (string->list needle))              (haystack (string->list haystack)))     (cond ((null? needle) 1)           ((null? haystack) 0)           ((char=? (car needle) (car haystack))             (+ (loop (cdr needle) (cdr haystack))                (loop needle (cdr haystack))))           (else (loop needle (cdr haystack))))))```

The first two `cond` clauses check for termination: if the needle is empty, a match has been found, but if the haystack is empty when the needle is not, matching failed. In the third `cond` clause, where the first characters of needle and haystack match, count the number of times the remainder of the needle and the remainder of the haystack match, and the last two `cond` clauses also count the number of times the needle is found in the remainder of the haystack. Fortunately, the code is simpler than this long-winded explanation. Here are some examples:

```> (count-all-matches "cat" "catapult") 3 > (count-all-matches "cap" "catapult") 2 > (count-all-matches "cut" "catapult") 1 > (count-all-matches "cup" "catapult") 0```

You can run the program at http://ideone.com/SlYKiF.

Advertisements

Pages: 1 2

### 8 Responses to “Count All Matches”

1. Francesco said

Haskell:

```import Control.Monad (filterM)

f n h = length . filter (== n) . filterM (const [True, False]) \$ h
```
2. Paul said

In Python.

```def matches(m, txt):
if not m:
return 1
if not txt:
return 0
n = matches(m, txt[1:])
if m == txt:
n += matches(m[1:], txt[1:])
return n
```
3. Sergei said

(defun count-all-matches (substr text)
(labels ((cam (ss tt)
(let ((count 0))
(cond ((null ss) 1)
((null tt) 0)
(t (loop while (setq tt (member (car ss) tt)) do
(incf count (cam (subseq ss 1) (subseq tt 1)))
(setq tt (subseq tt 1)))
count)))))
(cam (coerce substr ‘list) (coerce text ‘list))))))

4. Scott said
```       private static int numSubStrings(String sub, String full) {
char[] subArray = sub.toCharArray();
int[] found = new int[subArray.length];

for(char c : full.toCharArray()){
if(c == subArray){
found++;
}
else{
for(int i = 1; i < subArray.length; i++){
if(c == subArray[i] && found[i-1] > 0){
found[i] += found[i-1];
break;
}
}
}
}
return found[found.length-1];
}
```
5. matthew said

My initial C++ solution was like Scott’s, but there were some problems with eg. “count aaaa aaaaaaaa” (the perils of imperative programming). The following seems to works (and when applied to the above, the intermediate arrays of counts make a nice illustration of Pascal’s triangle). It’s sort of a compact memoized/dynamic programming version of the recursive solution (and a good deal more efficient than generating all possible substrings and comparing each one with the target):

```#include <string.h>
#include <stdio.h>
#include <vector>
int main(int argc, char *argv[])
{
char *s = argv, *t = argv;
int slen = strlen(s), tlen = strlen(t);
std::vector<int> a(slen+1);
a = 1;
for (int i = 0; i < tlen; i++) {
for (int j = slen; j > 0; j--) {
if (t[i] == s[j-1]) {
a[j] += a[j-1];
}
}
for (int i = 0; i < slen+1; i++) {
printf("%d%s", a[i],(i<slen)?" ":"\n");
}
}
printf("%d\n", a[slen]);
}

\$ ./count aaaa aaaaaaaa
1 1 0 0 0
1 2 1 0 0
1 3 3 1 0
1 4 6 4 1
1 5 10 10 5
1 6 15 20 15
1 7 21 35 35
1 8 28 56 70
70
```
6. Scott said

My previous solution fails for duplicate letters in the sub string e.g ‘tat’ –> ‘tatapult’. This corrects that mistake

```private static int numSubStrings(String sub, String full) {
char[] subArray = sub.toCharArray();
int[] found = new int[subArray.length];

for(char c : full.toCharArray()){
for(int i = 0; i < subArray.length; i++){
if(i == 0 && c == subArray){
found++;
}
else if(c == subArray[i] && found[i-1] > 0){
found[i] += found[i-1];
}
}
}
return found[found.length-1];
}
```
7. Mike said

Python.

```def count_all_matches(s, t):
def cam(s, t):
if s:
return sum(cam(s[1:], t[i+1:]) for i in range(len(t)) if s == t[i])
return 1
return cam(s, t) if s else 0
```

If t is very long, you might want to preprocess it to remove characters that are not in s.

I think this is equivalent to Francesco’s Haskell:

```def count(s, t):
u = tuple(s)
return sum(u == v for v in it.combinations(t, len(u)))
```
8. Jan Van lent said

Another Haskell solution.

```cam [] _ = 1
cam _ [] = 0
cam xxs@(x:xs) (y:ys) = if x == y then m + n else n
where m = cam xs ys
n = cam xxs ys
```