# Count occurrences of a substring

Count occurrences of a substring
You are encouraged to solve this task according to the task description, using any language you may know.

Create a function,   or show a built-in function,   to count the number of non-overlapping occurrences of a substring inside a string.

The function should take two arguments:

•   the first argument being the string to search,   and
•   the second a substring to be searched for.

It should return an integer count.

```print countSubstring("the three truths","th")
3

// do not count substrings that overlap with previously-counted substrings:
print countSubstring("ababababab","abab")
2```

The matching should yield the highest number of non-overlapping matches.

In general, this essentially means matching from left-to-right or right-to-left   (see proof on talk page).

## 11l

```print(‘the three truths’.count(‘th’))
print(‘ababababab’.count(‘abab’))```
Output:
```3
2
```

## 360 Assembly

The program uses two ASSIST macros (XDECO,XPRNT) to keep the code as short as possible.

```*        Count occurrences of a substring  05/07/2016
COUNTSTR CSECT
USING  COUNTSTR,R13       base register
B      72(R15)            skip savearea
DC     17F'0'             savearea
STM    R14,R12,12(R13)    prolog
ST     R13,4(R15)         "
ST     R15,8(R13)         "
LR     R13,R15            "
MVC    HAYSTACK,=CL32'the three truths'
MVC    LENH,=F'17'        lh=17
MVC    NEEDLE,=CL8'th'    needle='th'
MVC    LENN,=F'2'         ln=2
BAL    R14,SHOW           call show
MVC    HAYSTACK,=CL32'ababababab'
MVC    LENH,=F'11'        lh=11
MVC    NEEDLE,=CL8'abab'  needle='abab'
MVC    LENN,=F'4'         ln=4
BAL    R14,SHOW           call show
L      R13,4(0,R13)       epilog
LM     R14,R12,12(R13)    "
XR     R15,R15            "
BR     R14                exit
HAYSTACK DS     CL32               haystack
NEEDLE   DS     CL8                needle
LENH     DS     F                  length(haystack)
LENN     DS     F                  length(needle)
*------- ----   show---------------------------------------------------
SHOW     ST     R14,SAVESHOW       save return address
BAL    R14,COUNT          count(haystack,needle)
LR     R11,R0             ic=count(haystack,needle)
MVC    PG(20),HAYSTACK    output haystack
MVC    PG+20(5),NEEDLE    output needle
XDECO  R11,PG+25          output ic
XPRNT  PG,80              print buffer
SAVESHOW DS     A                  return address of caller
PG       DC     CL80' '            buffer
*------- ----   count--------------------------------------------------
COUNT    ST     R14,SAVECOUN       save return address
SR     R7,R7              n=0
LA     R6,1               istart=1
L      R10,LENH           lh
S      R10,LENN           ln
LA     R10,1(R10)         lh-ln+1
LOOPI    CR     R6,R10             do istart=1 to lh-ln+1
BH     ELOOPI
LA     R8,NEEDLE          @needle
L      R9,LENN            ln
LA     R4,HAYSTACK-1      @haystack[0]
AR     R4,R6              +istart
LR     R5,R9              ln
CLCL   R4,R8              if substr(haystack,istart,ln)=needle
BNE    NOTEQ
LA     R7,1(R7)           n=n+1
A      R6,LENN            istart=istart+ln
NOTEQ    LA     R6,1(R6)           istart=istart+1
B      LOOPI
ELOOPI   LR     R0,R7              return(n)
SAVECOUN DS     A                  return address of caller
*        ----   -------------------------------------------------------
YREGS
END    COUNTSTR```
Output:
```the three truths    th              3
ababababab          abab            2
```

## 8080 Assembly

The routine `subcnt` takes the string pointer in `HL` and the substring pointer in `BC`, and returns a 16-bit count in `DE`.

```	org	100h
jmp	demo
;;;	Count non-overlapping substrings (BC) in string (HL)
;;;	Returns amount of matches in DE
subcnt:	lxi	d,0	; Amount of matches
s_scan:	mov	a,m	; Get current character
ana	a	; End of string?
rz		; Then stop
push	b	; Keep start of substring search
push	h 	; Keep current location in string
s_cmp:	ldax	b	; Get character from substring
cmp	m	; Compare to curent charracter of search string
inx	h
jz	s_cmp	; Keep going if they were equal
ana	a	; Did we reach the end of the substring?
jz	s_find	; If so, we found a match
pop	h	; Otherwise, no match - restore search position
pop	b	; Restore start of substring
inx	h	; Try next position
jmp	s_scan
s_find:	inx	d	; We found a match
pop	b	; Discard start of the search, keep going after match
pop 	b	; Restore start of substring
dcx	h	; The comparison routine overshoots by one
jmp	s_scan
;;;	Test on a few strings
demo:	lxi	h,pairs
loop:	mov	e,m	; Load string pointer
inx	h
mov	d,m
inx	h
mov	a,d	; If 0, stop
ora	e
rz
mov	c,m	; Load substring pointer
inx	h
mov	b,m
inx	h
push	h	; Save example pointer
xchg		; Put string pointer in HL
call	subcnt	; Count substrings
mvi	a,'0'	; Assuming output is <10, print output
add	e	; (This is true for all examples, and a proper numeric
mov	e,a	; output routine is big and not relevant.)
mvi	c,2	; CP/M character output
call	5
pop	h	; Restore example pointer
jmp	loop
pairs:	dw	str1,sub1,str2,sub2,str3,sub3,0
str1:	db	'the three truths',0
sub1:	db	'th',0		; result should be 3
str2:	db	'ababababab',0
sub2:	db	'abab',0	; result should be 2
str3:	db	'cat',0
sub3:	db	'dog',0		; result should be 0```
Output:
`320`

## 8086 Assembly

```	cpu	8086
org	100h
section	.text
jmp	demo
;;;	Count non-overlapping substrings [ES:DI] in [DS:SI]
;;;	Return count in AX
subcnt:	xor	ax,ax		; Set count to 0
xor	dl,dl		; Zero to compare to
mov	bp,di		; Keep copy of substring pointer
.scan:	cmp	dl,[si]		; End of string?
je	.out		; Then we're done
mov	bx,si		; Keep copy of search position
mov	di,bp		; Start at beginning of substring
.cmp:	xor	cx,cx
dec	cx
repe	cmpsb		; Scan until no match
dec	si		; Go to first non-match
dec	di
cmp	dl,[es:di]	; Reached end of substring?
je	.match		; Then we found a match
mov	si,bx 		; If not, continue searching one
inc	si		; position further
jmp	.scan
.match:	inc	ax		; Found a match - increment count
jmp	.scan
.out:	ret
;;;	Test the routine on a few examples
demo:	mov	si,pairs
.loop:	lodsw			; Load string pointer
test	ax,ax		; If 0, stop
jz	.out
xchg	dx,ax
xchg	di,ax
push	si		; Keep example pointer
xchg	si,dx
call	subcnt		; Count substrings
call	prax		; Print amount of substrings
pop	si		; Restore example pointer
jmp	.loop
.out:	ret
;;;	Print AX as number
prax:	mov	bx,num		; Pointer to end of number string
mov	cx,10 		; Divisor
.dgt:	xor	dx,dx		; Divide by 10
div	cx
dec	bx		; Store digit
mov	[bx],dl
test	ax,ax		; If number not zero yet
jnz	.dgt		; Find rest of digits
mov	dx,bx		; Print number string
mov	ah,9
int	21h
ret
section	.data
db	'*****'		; Output number placeholder
num:	db	' \$'
;;;	Examples
pairs:	dw	.str1,.sub1,.str2,.sub2,.str3,.sub3,0
.str1:	db	'the three truths',0
.sub1:	db	'th',0		; result should be 3
.str2:	db	'ababababab',0
.sub2:	db	'abab',0	; result should be 2
.str3:	db	'cat',0
.sub3:	db	'dog',0		; result should be 0
```
Output:
`3 2 0`

## AArch64 Assembly

Works with: as version Raspberry Pi 3B version Buster 64 bits
or android 64 bits with application Termux
```/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program strcptsub64.s   */

/************************************/
/* Constantes                       */
/************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"

/************************************/
/* Initialized data                 */
/************************************/
.data
szMessResult:         .asciz "Result: "
szString:             .asciz "the three truths"
szSubString:          .asciz "th"
szString1:             .asciz "ababababab"
szSubString1:          .asciz "abab"
szCarriageReturn:     .asciz "\n"
szMessStart:          .asciz "Program 64 bits start.\n"
/************************************/
/* UnInitialized data               */
/************************************/
.bss
sZoneConv:            .skip 24
/************************************/
/*  code section                    */
/************************************/
.text
.global main
main:                      // entry of program
bl affichageMess
bl countSubString
bl countSubString

100:                       // standard end of the program
mov x0, #0             // return code
mov x8, #EXIT          // request to exit program
svc 0                  // perform the system call
/***************************************************/
/*   count sub string of string                    */
/***************************************************/
/* r0 contains a string */
/* r1 contains a substring */
/* r0 return substring count */
countSubString:
stp x1,lr,[sp,-16]!
stp x2,x3,[sp,-16]!
stp x4,x5,[sp,-16]!
stp x6,x7,[sp,-16]!
mov x4,#0            // counter
mov x3,#0            // index string
mov x5,#0            // index substring
1:
ldrb w6,[x0,x5]      // load byte of string
ldrb w7,[x1,x3]      // load byte of substring
cmp x6,x7            // compare byte
bne 2f               // not equal
cmp x6,#0            // string end ?
beq 3f               // yes
add x5,x5,#1         // else increment index
b 1b                 // and loop
2:                       // characters not equal
cmp x6,#0            // end string ?
beq 4f
cmp x7,#0            // end substring ?
csel x4,x6,x4,eq     // yes -> increment counter
mov x3,#0            // raz index substring
add x5,x5,#1         // increment string index
b 1b                 // and loop
3:                       // end string and end substring
4:                       // result display
mov x0,x4
bl conversion10
bl affichageMess
bl affichageMess
bl affichageMess

mov x0,x4
100:
ldp x6,x7,[sp],16
ldp x4,x5,[sp],16
ldp x2,x3,[sp],16
ldp x1,lr,[sp],16
ret
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeARM64.inc"```
Output:
```Program 64 bits start.
Result: 3
Result: 2
```

## Action!

```BYTE FUNC CountSubstring(CHAR ARRAY s,sub)
BYTE i,j,res,found

i=1 res=0
WHILE i-1+sub(0)<=s(0)
DO
found=1
FOR j=1 TO sub(0)
DO
IF s(j+i-1)#sub(j) THEN
found=0
EXIT
FI
OD

IF found=1 THEN
i==+sub(0)
res==+1
ELSE
i==+1
FI
OD
RETURN (res)

PROC Test(CHAR ARRAY s,sub)
BYTE c

c=CountSubstring(s,sub)
PrintF("%B ""%S"" in ""%S""%E",c,sub,s)
RETURN

PROC Main()
Test("the three truths","th")
Test("ababababab","abab")
Test("11111111","11")
Test("abcdefg","123")
RETURN```
Output:
```3 "th" in "the three truths"
2 "abab" in "ababababab"
4 "11" in "11111111"
0 "123" in "abcdefg"
```

```with Ada.Strings.Fixed, Ada.Integer_Text_IO;

procedure Substrings is
begin
Pattern => "th"));
Pattern => "abab"));
end Substrings;
```
Output:
`          3          2`

## ALGOL 68

Works with: ALGOL 68 version Revision 1 - no extensions to language used.
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny.

Algol68 has no build in function to do this task, hence the next to create a count string in string routine.

```#!/usr/local/bin/a68g --script #

PROC count string in string = (STRING needle, haystack)INT: (
INT start:=LWB haystack, next, out:=0;
FOR count WHILE string in string(needle, next, haystack[start:]) DO
start+:=next+UPB needle-LWB needle;
out:=count
OD;
out
);

printf((\$d" "\$,
count string in string("th", "the three truths"),    # expect 3 #
count string in string("abab", "ababababab"),        # expect 2 #
count string in string("a*b", "abaabba*bbaba*bbab"), # expect 2 #
\$l\$
))```
```3 2 2
```

## Apex

Apex example for 'Count occurrences of a substring'.

```String substr = 'ABC';
String str = 'ABCZZZABCYABCABCXXABC';
Integer substrLen = substr.length();
Integer count = 0;
Integer index = str.indexOf(substr);
while (index >= 0) {
count++;
str = str.substring(index+substrLen);
index = str.indexOf(substr);
}
System.debug('Count String : '+count);```
```Count String : 5
```

## APL

Works with: Dyalog APL
```csubs←{0=x←⊃⍸⍺⍷⍵:0 ⋄ 1+⍺∇(¯1+x+⍴⍺)↓⍵}
```
Output:
```      'th' 'abab' 'dog' csubs¨ 'the three truths' 'ababababab' 'cat'
3 2 0```

## AppleScript

This is a good example of the kind of problem to which standard libraries (a regex library in this case) would offer most languages a simple and immediate solution. AppleScript, however, for want of various basics like regex and math library functions, can require scripters to draw on the supplementary resources of Bash, using the built-in do shell script function.

A slightly faster approach to seeking outside library help has, however, become possible since OS X 10.10 added JavaScript as an osalang sibling for AppleScript. Rather than using the resources of Bash, we can more quickly use AppleScript's built in ObjC interface to pass a subproblem over to the more richly endowed JavaScript core of JavaScript for Automation.

Here we use a generic evalOSA(language, code) function to apply a JavaScript for Automation regex to a pair of AppleScript strings, using OSAKit.

```use framework "OSAKit"

on run
{countSubstring("the three truths", "th"), ¬
countSubstring("ababababab", "abab")}
end run

on countSubstring(str, subStr)
return evalOSA("JavaScript", "var matches = '" & str & "'" & ¬
".match(new RegExp('" & subStr & "', 'g'));" & ¬
"matches ? matches.length : 0") as integer
end countSubstring

-- evalOSA :: ("JavaScript" | "AppleScript") -> String -> String
on evalOSA(strLang, strCode)

set ca to current application
set oScript to ca's OSAScript's alloc's initWithSource:strCode ¬
|language|:(ca's OSALanguage's languageForName:(strLang))

set {blnCompiled, oError} to oScript's compileAndReturnError:(reference)

if blnCompiled then
set {oDesc, oError} to oScript's executeAndReturnError:(reference)
if (oError is missing value) then return oDesc's stringValue as text
end if

return oError's NSLocalizedDescription as text
end evalOSA
```
Output:
```{3, 2}
```

The above assertions notwithstanding, it's always been possible to use AppleScript's text item delimiters for this purpose with its native strings, except that the TIDs have only observed the current considering/ignoring state with the 'unicode text' class, which was introduced around Mac OS X 10.4 and became AppleScript's only native text class with the introduction of AppleScript 2.0 in Mac OS X 10.5.

```on countSubstring(theString, theSubstring)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to theSubstring
set substringCount to (count theString's text items) - 1
set AppleScript's text item delimiters to astid

return substringCount
end countSubstring

{countSubstring("the three truths", "th"), countSubstring("ababababab", "abab")}
```
Output:
```{3, 2}
```

## ARM Assembly

Works with: as version Raspberry Pi
or android 32 bits with application Termux
```/* ARM assembly Raspberry PI  */
/*  program strcptsub.s   */

/************************************/
/* Constantes                       */
/************************************/
/* for this file see task include a file in language ARM assembly*/
.include "../constantes.inc"

/************************************/
/* Initialized data                 */
/************************************/
.data
szMessResult:         .asciz "Result: "
szString:             .asciz "the three truths"
szSubString:          .asciz "th"
szString1:             .asciz "ababababab"
szSubString1:          .asciz "abab"
szCarriageReturn:     .asciz "\n"
szMessStart:          .asciz "Program 32 bits start.\n"
/************************************/
/* UnInitialized data               */
/************************************/
.bss
sZoneConv:            .skip 24
/************************************/
/*  code section                    */
/************************************/
.text
.global main
main:                      @ entry of program
bl affichageMess
bl countSubString
bl countSubString

100:                       @ standard end of the program
mov r0, #0             @ return code
mov r7, #EXIT          @ request to exit program
svc 0                  @ perform the system call
/***************************************************/
/*   count sub string of string                    */
/***************************************************/
/* r0 contains a string */
/* r1 contains a substring */
/* r0 return substring count */
countSubString:
push {r1-r7,lr}      @ save registers
mov r4,#0            @ counter
mov r3,#0            @ index string
Mov r5,#0            @ index substring
1:
ldrb r6,[r0,r5]      @ load byte of string
ldrb r7,[r1,r3]      @ load byte of substring
cmp r6,r7            @ compare byte
bne 2f               @ not equal
cmp r6,#0            @ string end ?
beq 3f               @ yes
add r5,r5,#1         @ else increment index
b 1b                 @ and loop
2:                       @ characters not equal
cmp r6,#0            @ end string ?
beq 4f
cmp r7,#0            @ end substring ?
addeq r4,r4,#1       @ yes -> increment counter
mov r3,#0            @ raz index substring
add r5,r5,#1         @ increment string index
b 1b                 @ and loop
3:                       @ end string and end substring
4:                       @ result display
mov r0,r4
bl conversion10
bl affichageMess
bl affichageMess
bl affichageMess

mov r0,r4
100:
pop {r1-r7,pc}
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
/* for this file see task include a file in language ARM assembly*/
.include "../affichage.inc"```
Output:
```Program 32 bits start.
Result: 3
Result: 2
```

## Arturo

```countOccurrences: function [str, substr]-> size match str substr

loop [["the three truths" "th"] ["ababababab" "abab"]] 'pair ->
print [
~"occurrences of '|last pair|' in '|first pair|':"
countOccurrences first pair last pair
]
```
Output:
```occurrences of 'th' in 'the three truths': 3
occurrences of 'abab' in 'ababababab': 2```

## AutoHotkey

While it is simple enough to parse the string, AutoHotkey has a rather unconventional method which outperforms this. StringReplace sets the number of replaced strings to ErrorLevel.

```MsgBox % countSubstring("the three truths","th") ; 3
MsgBox % countSubstring("ababababab","abab")     ; 2

CountSubstring(fullstring, substring){
StringReplace, junk, fullstring, %substring%, , UseErrorLevel
return errorlevel
}
```

## AWK

```#
# countsubstring(string, pattern)
#   Returns number of occurrences of pattern in string
#   Pattern treated as a literal string (regex characters not expanded)
#
function countsubstring(str, pat,    len, i, c) {
c = 0
if( ! (len = length(pat) ) )
return 0
while(i = index(str, pat)) {
str = substr(str, i + len)
c++
}
return c
}
#
# countsubstring_regex(string, regex_pattern)
#   Returns number of occurrences of pattern in string
#   Pattern treated as regex
#
function countsubstring_regex(str, pat,    c) {
c = 0
c += gsub(pat, "", str)
return c
}
BEGIN {
print countsubstring("[do&d~run?d!run&>run&]", "run&")
print countsubstring_regex("[do&d~run?d!run&>run&]", "run[&]")
print countsubstring("the three truths","th")
}
```
Output:
```\$ awk -f countsubstring.awk
2
2
3
```

## BaCon

```FUNCTION Uniq_Tally(text\$, part\$)
LOCAL x
WHILE TALLY(text\$, part\$)
INCR x
text\$ = MID\$(text\$, INSTR(text\$, part\$)+LEN(part\$))
WEND
RETURN x
END FUNCTION

PRINT "the three truths - th: ", Uniq_Tally("the three truths", "th")
PRINT "ababababab - abab: ", Uniq_Tally("ababababab", "abab")
```
Output:
```the three truths - th: 3
ababababab - abab: 2
```

## BASIC

Works with: QBasic

In FreeBASIC, this needs to be compiled with `-lang qb` or `-lang fblite`.

```DECLARE FUNCTION countSubstring& (where AS STRING, what AS STRING)

PRINT "the three truths, th:", countSubstring&("the three truths", "th")
PRINT "ababababab, abab:", countSubstring&("ababababab", "abab")

FUNCTION countSubstring& (where AS STRING, what AS STRING)
DIM c AS LONG, s AS LONG
s = 1 - LEN(what)
DO
s = INSTR(s + LEN(what), where, what)
IF 0 = s THEN EXIT DO
c = c + 1
LOOP
countSubstring = c
END FUNCTION
```
Output:
```the three truths, th:        3
ababababab, abab:            2
```

### Applesoft BASIC

```10 F\$ = "TH"
20 S\$ = "THE THREE TRUTHS"
30 GOSUB 100"COUNT SUBSTRING
40 PRINT R
50 F\$ = "ABAB"
60 S\$ = "ABABABABAB"
70 GOSUB 100"COUNT SUBSTRING
80 PRINT R
90 END

100 R = 0
110 F = LEN(F\$)
120 S = LEN(S\$)
130 IF F > S THEN RETURN
140 IF F = 0 THEN RETURN
150 IF F = S AND F\$ = S\$ THEN R = 1 : RETURN
160 FOR I = 1 TO S - F
170     IF F\$ = MID\$(S\$, I, F) THEN R = R + 1 : I = I + F - 1
180 NEXT I
190 RETURN```

### BASIC256

Translation of: Run BASIC
```print countSubstring("the three truths","th")
print countSubstring("ababababab","abab")
end

function countSubstring(s\$,find\$)
i = 1
while instr(s\$,find\$,i) <> 0
countSubstring += 1
i = instr(s\$,find\$,i) + length(find\$)
end while
end function```
Output:
`Igual que la entrada de Run BASIC.`

### Chipmunk Basic

Works with: Chipmunk Basic version 3.6.4
Works with: Applesoft BASIC
Works with: MSX_BASIC
Works with: PC-BASIC version any
Works with: QBasic
Translation of: Applesoft BASIC
```10 CLS : REM  10 HOME for Applesoft BASIC
20 F\$ = "TH"
30 S\$ = "THE THREE TRUTHS"
40 GOSUB 110: REM COUNT SUBSTRING
50 PRINT R
60 F\$ = "ABAB"
70 S\$ = "ABABABABAB"
80 GOSUB 110: REM COUNT SUBSTRING
90 PRINT R
100 END
110 R = 0
120 F = LEN(F\$)
130 S = LEN(S\$)
140 IF F > S THEN RETURN
150 IF F = 0 THEN RETURN
160 IF F = S AND F\$ = S\$ THEN R = 1: RETURN
170 FOR I = 1 TO S - F
180   IF F\$ = MID\$(S\$, I, F) THEN R = R + 1: I = I + F - 1
190 NEXT I
200 RETURN
```

### GW-BASIC

The Chipmunk Basic solution works without any changes.

### IS-BASIC

```100 INPUT PROMPT "String:    ":TXT\$
110 INPUT PROMPT "Substring: ":SUB\$
120 PRINT COUNT(LCASE\$(TXT\$),LCASE\$(SUB\$))
130 DEF COUNT(TXT\$,SUB\$)
140   LET N=0:LET PO=1
150   DO
160     LET PO=POS(TXT\$,SUB\$,PO)
170     IF PO THEN LET N=N+1:LET PO=PO+LEN(SUB\$)
180   LOOP UNTIL PO=0
190   LET COUNT=N
200 END DEF```

### MSX Basic

The Chipmunk Basic solution works without any changes.

### Sinclair ZX81 BASIC

Works with 1k of RAM.

``` 10 LET S\$="THE THREE TRUTHS"
20 LET U\$="TH"
30 GOSUB 100
40 PRINT N
50 LET S\$="ABABABABAB"
60 LET U\$="ABAB"
70 GOSUB 100
80 PRINT N
90 STOP
100 LET N=0
110 LET I=0
120 LET I=I+1
130 IF I+LEN U\$>LEN S\$ THEN RETURN
140 IF S\$(I TO I+LEN U\$-1)<>U\$ THEN GOTO 120
150 LET N=N+1
160 LET I=I+LEN U\$
170 GOTO 130
```

### True BASIC

Translation of: QBasic
```FUNCTION countsubstring(where\$, what\$)
LET c = 0
LET s = 1-LEN(what\$)
DO
LET s = POS(where\$,what\$,s+LEN(what\$))
IF 0 = s THEN EXIT DO
LET c = c+1
LOOP
LET countsubstring = c
END FUNCTION

PRINT "the three truths, th:", countSubstring("the three truths", "th")
PRINT "ababababab, abab:", countSubstring("ababababab", "abab")
END
```

### Yabasic

Translation of: Run BASIC
```print countSubstring("the three truths","th")
print countSubstring("ababababab","abab")
end

sub countSubstring(s\$,find\$)
countSubstring = 0
i = 1
while instr(s\$,find\$,i) <> 0
countSubstring = countSubstring + 1
i = instr(s\$,find\$,i) + len(find\$)
end while
return countSubstring
end sub```
Output:
`Igual que la entrada de Run BASIC.`

## Batch File

```@echo off
setlocal enabledelayedexpansion

::Main
call :countString "the three truths","th"
call :countString "ababababab","abab"
pause>nul
exit /b
::/Main

::Procedure
:countString
set input=%~1
set cnt=0

:count_loop
set trimmed=!input:*%~2=!
if "!trimmed!"=="!input!" (echo.!cnt!&goto :EOF)
set input=!trimmed!
set /a cnt+=1
goto count_loop```
Output:
```3
2```

## BBC BASIC

```      tst\$ = "the three truths"
sub\$ = "th"
PRINT ; FNcountSubstring(tst\$, sub\$) " """ sub\$ """ in """ tst\$ """"
tst\$ = "ababababab"
sub\$ = "abab"
PRINT ; FNcountSubstring(tst\$, sub\$) " """ sub\$ """ in """ tst\$ """"
END

DEF FNcountSubstring(A\$, B\$)
LOCAL I%, N%
I% = 1 : N% = 0
REPEAT
I% = INSTR(A\$, B\$, I%)
IF I% THEN N% += 1 : I% += LEN(B\$)
UNTIL I% = 0
= N%
```
Output:
```3 "th" in "the three truths"
2 "abab" in "ababababab"```

## BCPL

```get "libhdr"

let countsubstr(str, match) = valof
\$(  let i, count = 1, 0
while i <= str%0 do
test valof
\$(  for j = 1 to match%0
unless match%j = str%(i+j-1)
resultis false
resultis true
\$)
then
\$(  count := count + 1
i := i + match%0
\$)
else
i := i + 1
resultis count
\$)

let show(str, match) be
writef("*"%S*" in *"%S*": %N*N",
match, str, countsubstr(str, match))

let start() be
\$(  show("the three truths", "th")
show("ababababab", "abab")
show("cat", "dog")
\$)```
Output:
```"th" in "the three truths": 3
"abab" in "ababababab": 2
"dog" in "cat": 0```

## BQN

`/𝕨⍷𝕩` finds locations of substrings, rest of the function suppresses overlapping substrings.

```Find←{i←/𝕨⍷𝕩, i/˜i≥»0≤◶⟨⊣,(≠𝕨)+⊢⟩`i}

•Show "abab" Find "ababababab"
•Show "th" Find "the three truths"
```
```2
3
```

Using strings.bqn from bqn-libs, another solution is `Find←+´Locate`, since `Locate` performs a non-overlapping search.

## Bracmat

```  ( count-substring
=   n S s p
.     0:?n:?p
& !arg:(?S.?s)
& @( !S
:   ?
( [!p ? !s [?p ?
& !n+1:?n
& ~
)
)
| !n
)
& out\$(count-substring\$("the three truths".th))
& out\$(count-substring\$(ababababab.abab))
& ;```
Output:
```3
2```

## C

```#include <stdio.h>
#include <string.h>

int match(const char *s, const char *p, int overlap)
{
int c = 0, l = strlen(p);

while (*s != '\0') {
if (strncmp(s++, p, l)) continue;
if (!overlap) s += l - 1;
c++;
}
return c;
}

int main()
{
printf("%d\n", match("the three truths", "th", 0));
printf("overlap:%d\n", match("abababababa", "aba", 1));
printf("not:    %d\n", match("abababababa", "aba", 0));
return 0;
}
```

Alternate version:

```#include <stdio.h>
#include <string.h>

// returns count of non-overlapping occurrences of 'sub' in 'str'
int countSubstring(const char *str, const char *sub)
{
int length = strlen(sub);
if (length == 0) return 0;
int count = 0;
for (str = strstr(str, sub); str; str = strstr(str + length, sub))
++count;
return count;
}

int main()
{
printf("%d\n", countSubstring("the three truths", "th"));
printf("%d\n", countSubstring("ababababab", "abab"));
printf("%d\n", countSubstring("abaabba*bbaba*bbab", "a*b"));

return 0;
}
```
Output:
```3
2
2
```

## C#

```using System;

class SubStringTestClass
{
public static int CountSubStrings(this string testString, string testSubstring)
{
int count = 0;

if (testString.Contains(testSubstring))
{
for (int i = 0; i < testString.Length; i++)
{
if (testString.Substring(i).Length >= testSubstring.Length)
{
bool equals = testString.Substring(i, testSubstring.Length).Equals(testSubstring);
if (equals)
{
count++;
i += testSubstring.Length - 1;  // Fix: Don't count overlapping matches
}
}
}
}
return count;
}
}```

Using C# 6.0's expression-bodied member, null-conditional operator, and coalesce operator features:

```using System;
class SubStringTestClass
{
public static int CountSubStrings(this string testString, string testSubstring) =>
testString?.Split(new [] { testSubstring }, StringSplitOptions.None)?.Length - 1 ?? 0;
}```

## C++

```#include <iostream>
#include <string>

// returns count of non-overlapping occurrences of 'sub' in 'str'
int countSubstring(const std::string& str, const std::string& sub)
{
if (sub.length() == 0) return 0;
int count = 0;
for (size_t offset = str.find(sub); offset != std::string::npos;
offset = str.find(sub, offset + sub.length()))
{
++count;
}
return count;
}

int main()
{
std::cout << countSubstring("the three truths", "th")    << '\n';
std::cout << countSubstring("ababababab", "abab")        << '\n';
std::cout << countSubstring("abaabba*bbaba*bbab", "a*b") << '\n';

return 0;
}
```
Output:
```3
2
2
```

## Clojure

Use a sequence of regexp matches to count occurrences.

```(defn re-quote
"Produces a string that can be used to create a Pattern
that would match the string text as if it were a literal pattern.
Metacharacters or escape sequences in text will be given no special
meaning"
[text]
(java.util.regex.Pattern/quote text))

(defn count-substring [txt sub]
(count (re-seq (re-pattern (re-quote sub)) txt)))
```

Use the trick of blank replacement and maths to count occurrences.

```(defn count-substring1 [txt sub]
(/ (- (count txt) (count (.replaceAll txt sub "")))
(count sub)))
```

A Java 8 stream-based solution, which should avoid creation of temporary strings (though it will produce temporary MatchResult instances).

```(defn count-substring2 [txt sub]
(-> sub
(re-quote)
(re-pattern)
(re-matcher txt)
(.results)
(.count)))
```

## COBOL

`INSPECT` can be used for this task without having to create a function.

```       IDENTIFICATION DIVISION.
PROGRAM-ID. testing.

DATA DIVISION.
WORKING-STORAGE SECTION.
01  occurrences             PIC 99.

PROCEDURE DIVISION.
INSPECT "the three truths" TALLYING occurrences FOR ALL "th"
DISPLAY occurrences

MOVE 0 TO occurrences
INSPECT "ababababab" TALLYING occurrences FOR ALL "abab"
DISPLAY occurrences

MOVE 0 TO occurrences
INSPECT "abaabba*bbaba*bbab" TALLYING occurrences
FOR ALL "a*b"
DISPLAY occurrences

GOBACK
.
```
Output:
```03
02
02
```

## CoffeeScript

```countSubstring = (str, substr) ->
n = 0
i = 0
while (pos = str.indexOf(substr, i)) != -1
n += 1
i = pos + substr.length
n

console.log countSubstring "the three truths", "th"
console.log countSubstring "ababababab", "abab"
```

## Common Lisp

```(defun count-sub (str pat)
(loop with z = 0 with s = 0 while s do
(when (setf s (search pat str :start2 s))
(incf z) (incf s (length pat)))
finally (return z)))

(count-sub "ababa" "ab")  ; 2
(count-sub "ababa" "aba") ; 1
```

## Cowgol

```include "cowgol.coh";

sub countSubstring(str: [uint8], match: [uint8]): (count: uint8) is
count := 0;

while [str] != 0 loop
var find := match;
var loc := str;
while [loc] == [find] loop
find := @next find;
loc := @next loc;
end loop;
if [find] == 0 then
str := loc;
count := count + 1;
else
str := @next str;
end if;
end loop;
end sub;

print_i8(countSubstring("the three truths","th")); # should print 3
print_nl();
print_i8(countSubstring("ababababab","abab")); # should print 2
print_nl();
print_i8(countSubstring("cat","dog")); # should print 0
print_nl();```
Output:
```3
2
0```

## D

```void main() {
import std.stdio, std.algorithm;

"the three truths".count("th").writeln;
"ababababab".count("abab").writeln;
}
```
Output:
```3
2```

## Delphi

```program OccurrencesOfASubstring;

{\$APPTYPE CONSOLE}

uses StrUtils;

function CountSubstring(const aString, aSubstring: string): Integer;
var
lPosition: Integer;
begin
Result := 0;
lPosition := PosEx(aSubstring, aString);
while lPosition <> 0 do
begin
Inc(Result);
lPosition := PosEx(aSubstring, aString, lPosition + Length(aSubstring));
end;
end;

begin
Writeln(CountSubstring('the three truths', 'th'));
Writeln(CountSubstring('ababababab', 'abab'));
end.
```

## Draco

```proc countSubstring(*char string, substring) word:
word count;
*char pos, loc;

count := 0;
while string* /= '\e' do
pos := substring;
loc := string;
while loc* = pos* do
loc := loc + 1;
pos := pos + 1
od;
if pos* = '\e' then
string := loc;
count := count + 1
else
string := string + 1
fi
od;
count
corp

proc main() void:
writeln(countSubstring("the three truths", "th"));
writeln(countSubstring("ababababab", "abab"))
corp```
Output:
```3
2```

## Dyalect

```func countSubstring(str, val) {
var idx = 0
var count = 0
while true {
idx = str.IndexOf(val, idx)
if idx == -1 {
break
}
idx += val.Length()
count += 1
}
return count
}

print(countSubstring("the three truths", "th"))
print(countSubstring("ababababab", "abab"))```
Output:
```3
2```

## Déjà Vu

```!. count "the three truths" "th"
!. count "ababababab" "abab"```
Output:
```3
2```

## EasyLang

```func count str\$ pat\$ .
ind = 1
while ind + len pat\$ - 1 <= len str\$
if substr str\$ ind len pat\$ = pat\$
cnt += 1
ind += len pat\$
else
ind += 1
.
.
return cnt
.
print count "the three truths" "th"
print count "ababababab" "abab"
print count "11111111" "11"
print count "11111111" "12"
print count "12" "12"```

## EchoLisp

```;; from Racket
(define count-substring
(compose length regexp-match*))

(count-substring "aab" "graabaabdfaabgh") ;; substring
→ 3
(count-substring "/ .e/" "Longtemps je me suis couché de bonne heure") ;; regexp
→ 4
```

## EGL

Works with: EDT

The "remove and count the difference" and "manual loop" methods. Implementation includes protection from empty source and search strings.

```program CountStrings

function main()
SysLib.writeStdout("Remove and Count:");
SysLib.writeStdout(countSubstring("th", "the three truths"));
SysLib.writeStdout(countSubstring("abab", "ababababab"));
SysLib.writeStdout(countSubstring("a*b", "abaabba*bbaba*bbab"));
SysLib.writeStdout(countSubstring("a", "abaabba*bbaba*bbab"));
SysLib.writeStdout(countSubstring(" ", "abaabba*bbaba*bbab"));
SysLib.writeStdout(countSubstring("", "abaabba*bbaba*bbab"));
SysLib.writeStdout(countSubstring("a", ""));
SysLib.writeStdout(countSubstring("", ""));

SysLib.writeStdout("Manual Loop:");
SysLib.writeStdout(countSubstringWithLoop("th", "the three truths"));
SysLib.writeStdout(countSubstringWithLoop("abab", "ababababab"));
SysLib.writeStdout(countSubstringWithLoop("a*b", "abaabba*bbaba*bbab"));
SysLib.writeStdout(countSubstringWithLoop("a", "abaabba*bbaba*bbab"));
SysLib.writeStdout(countSubstringWithLoop(" ", "abaabba*bbaba*bbab"));
SysLib.writeStdout(countSubstringWithLoop("", "abaabba*bbaba*bbab"));
SysLib.writeStdout(countSubstringWithLoop("a", ""));
SysLib.writeStdout(countSubstringWithLoop("", ""));
end

function countSubstring(substr string in, str string in) returns(int)
if(str.length() > 0 and substr.length() > 0)
return (str.length() - str.replaceStr(subStr, "").length()) / subStr.length();
else
return 0;
end
end

function countSubstringWithLoop(substr string in, str string in) returns(int)
count int = 0;
loc, index int = 1;
strlen int = str.length();
substrlen int = substr.length();

if(strlen > 0 and substrlen > 0)
while(loc != 0 and index <= strlen)
loc = str.indexOf(substr, index);
if(loc > 0)
count += 1;
index = loc + substrlen;
end
end
end
return count;
end

end```
Output:
```Remove and Count:
3
2
2
7
0
0
0
0
Manual Loop:
3
2
2
7
0
0
0
0```

## Eiffel

```class
APPLICATION
inherit
ARGUMENTS
create
make
feature {NONE} -- Initialization
make
-- Run application.
do
occurance := 0
from
index := 1
until
index > text.count
loop
temp := text.fuzzy_index(search_for, index, 0)
if
temp /= 0
then
index := temp + search_for.count
occurance := occurance + 1
else
index := text.count + 1
end
end
print(occurance)
end

index:INTEGER
temp:INTEGER
occurance:INTEGER
text:STRING = "ababababab"
search_for:STRING = "abab"
end
```

## Elixir

```countSubstring = fn(_, "") -> 0
(str, sub) -> length(String.split(str, sub)) - 1 end

data = [ {"the three truths", "th"},
{"ababababab", "abab"},
{"abaabba*bbaba*bbab", "a*b"},
{"abaabba*bbaba*bbab", "a"},
{"abaabba*bbaba*bbab", " "},
{"abaabba*bbaba*bbab", ""},
{"", "a"},
{"", ""} ]

Enum.each(data, fn{str, sub} ->
IO.puts countSubstring.(str, sub)
end)
```
Output:
```3
2
2
7
0
0
0
0
```

## Erlang

```%% Count non-overlapping substrings in Erlang for the rosetta code wiki.
%% Implemented by J.W. Luiten

-module(substrings).
-export([main/2]).

%% String and Sub exhausted, count a match and present result
match([], [], _OrigSub, Acc) ->
Acc+1;

%% String exhausted, present result
match([], _Sub, _OrigSub, Acc) ->
Acc;

%% Sub exhausted, count a match
match(String, [], Sub, Acc) ->
match(String, Sub, Sub, Acc+1);

match([X|MainTail], [X|SubTail], Sub, Acc) ->
match(MainTail, SubTail, Sub, Acc);

%% First characters do not match. Keep scanning for sub in remainder of string
match([_X|MainTail], [_Y|_SubTail], Sub, Acc)->
match(MainTail, Sub, Sub, Acc).

main(String, Sub) ->
match(String, Sub, Sub, 0).
```

Command:

```substrings:main("ababababab","abab").
```
Output:
```2
```

Alternative using built in functions:

```main( String, Sub ) -> erlang:length( binary:split(binary:list_to_bin(String), binary:list_to_bin(Sub), [global]) ) - 1.
```

## Euphoria

```function countSubstring(sequence s, sequence sub)
integer from,count
count = 0
from = 1
while 1 do
from = match_from(sub,s,from)
if not from then
exit
end if
from += length(sub)
count += 1
end while
return count
end function

? countSubstring("the three truths","th")
? countSubstring("ababababab","abab")```
Output:
```3
2
```

## F#

"Remove and count the difference" method, as shown by J, Java, ...

```open System

let countSubstring (where :string) (what : string) =
match what with
| "" -> 0 // just a definition; infinity is not an int
| _ -> (where.Length - where.Replace(what, @"").Length) / what.Length

[<EntryPoint>]
let main argv =
let show where what =
printfn @"countSubstring(""%s"", ""%s"") = %d" where what (countSubstring where what)
show "the three truths" "th"
show "ababababab" "abab"
show "abc" ""
0
```
```countSubstring("the three truths", "th") = 3
countSubstring("ababababab", "abab") = 2
countSubstring("abc", "") = 0```

## Factor

```USING: math sequences splitting ;
: occurences ( seq subseq -- n ) split-subseq length 1 - ;
```

## Forth

```: str-count ( s1 len s2 len -- n )
2swap 0 >r
begin 2over search
while 2over nip /string
r> 1+ >r
repeat 2drop 2drop r> ;

s" the three truths" s" th" str-count .    \ 3
s" ababababab" s" abab" str-count .     \ 2
```

## Fortran

Works with: Fortran version 90 and later
```program Example
implicit none
integer :: n

n = countsubstring("the three truths", "th")
write(*,*) n
n = countsubstring("ababababab", "abab")
write(*,*) n
n = countsubstring("abaabba*bbaba*bbab", "a*b")
write(*,*) n

contains

function countsubstring(s1, s2) result(c)
character(*), intent(in) :: s1, s2
integer :: c, p, posn

c = 0
if(len(s2) == 0) return
p = 1
do
posn = index(s1(p:), s2)
if(posn == 0) return
c = c + 1
p = p + posn + len(s2) - 1
end do
end function
end program
```
Output:
```3
2
2```

## FreeBASIC

```' FB 1.05.0 Win64

Function countSubstring(s As String, search As String) As Integer
If s = "" OrElse search = "" Then Return 0
Dim As Integer count = 0, length = Len(search)
For i As Integer = 1 To Len(s)
If Mid(s, i, length) = Search Then
count += 1
i += length - 1
End If
Next
Return count
End Function

Print countSubstring("the three truths","th")
Print countSubstring("ababababab","abab")
Print countSubString("zzzzzzzzzzzzzzz", "z")
Print
Print "Press any key to quit"
Sleep```
Output:
``` 3
2
15
```

## FunL

```import util.Regex

def countSubstring( str, substr ) = Regex( substr ).findAllMatchIn( str ).length()

println( countSubstring("the three truths", "th") )
println( countSubstring("ababababab", "abab") )```
Output:
```3
2
```

## Fōrmulæ

Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.

Programs in Fōrmulæ are created/edited online in its website.

In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.

## FutureBasic

```window 1

local fn CountSubstring( string as CFStringRef, substring as CFStringRef ) as long
end fn = fn ArrayCount( fn StringComponentsSeparatedByString( string, substring ) ) - 1

print fn CountSubstring( @"the three truths", @"th" )
print fn CountSubstring( @"ababababab", @"abab" )

HandleEvents```
Output:
```3
2
```

## Gambas

Translation of: FreeBASIC
```Public Sub Main()

Print countSubstring("the three truths", "th")
Print countSubstring("ababababab", "abab")
Print countSubString("zzzzzzzzzzzzzzz", "z")

End

Function countSubstring(s As String, search As String) As Integer

If s = "" Or search = "" Then Return 0
Dim count As Integer = 0, length As Integer = Len(search)
For i As Integer = 1 To Len(s)
If Mid(s, i, length) = Search Then
count += 1
i += length - 1
End If
Next
Return count

End Function
```
Output:
`Same as FreeBASIC entry.`

## Go

Using strings.Count() method:

```package main
import (
"fmt"
"strings"
)

func main() {
fmt.Println(strings.Count("the three truths", "th")) // says: 3
fmt.Println(strings.Count("ababababab", "abab"))     // says: 2
}
```

## Groovy

Solution, uses the Groovy "find" operator (=~), and the Groovy-extended Matcher property "count":

```println (('the three truths' =~ /th/).count)
println (('ababababab' =~ /abab/).count)
println (('abaabba*bbaba*bbab' =~ /a*b/).count)
println (('abaabba*bbaba*bbab' =~ /a\*b/).count)
```
Output:
```3
2
9
2```

### Text-based solution

```import Data.Text hiding (length)

-- Return the number of non-overlapping occurrences of sub in str.
countSubStrs str sub = length \$ breakOnAll (pack sub) (pack str)

main = do
print \$ countSubStrs "the three truths" "th"
print \$ countSubStrs "ababababab" "abab"
```
Output:
```3
2
```

Alternatively, in a language built around currying, it might make more sense to reverse the suggested order of arguments.

```{-# LANGUAGE OverloadedStrings #-}

import Data.Text hiding (length)

--------- COUNT OF SUBSTRING INSTANCES IN A STRING -------

countAll :: Text -> Text -> Int
countAll needle haystack =
length
(breakOnAll needle haystack)

--------------------------- TEST -------------------------
main :: IO ()
main =
print \$
countAll "ab"
<\$> [ "ababababab",
"abelian absurdity",
"babel kebab"
]
```
Output:
`[5,2,2]`

### List-based solution

Even though list-based strings are not "the right" way of representing texts, the problem of counting subsequences in a list is generally useful.

```count :: Eq a => [a] -> [a] -> Int
count []  = error "empty substring"
count sub = go
where
go = scan sub . dropWhile (/= head sub)
scan _ [] = 0
scan [] xs = 1 + go xs
scan (x:xs) (y:ys) | x == y    = scan xs ys
| otherwise = go ys
```
Output:
```λ> count "th" "the three truths"
3
λ> count "abab" "ababababab"
2
λ> count [2,3] [1,2,1,2,3,4,3,2,3,4,3,2]
2
λ> count "123456" \$ foldMap show [1..1000000]
7```

### List-based solution using Data.List

The following solution is almost two times faster than the previous one.

```import Data.List (tails, stripPrefix)
import Data.Maybe (catMaybes)

count :: Eq a => [a] -> [a] -> Int
count sub = length . catMaybes . map (stripPrefix sub) . tails
```

## Icon and Unicon

```procedure main()
every A := ![ ["the three truths","th"], ["ababababab","abab"] ] do
write("The string ",image(A[2])," occurs as a non-overlapping substring ",
countSubstring!A , " times in ",image(A[1]))
end

procedure countSubstring(s1,s2) #: return count of non-overlapping substrings
c := 0
s1 ? while tab(find(s2)) do {
move(*s2)
c +:= 1
}
return c
end
```
Output:
```The string "th" occurs as a non-overlapping substring 3 times in "the three truths"
The string "abab" occurs as a non-overlapping substring 2 times in "ababababab"```

## J

```require'strings'
countss=: #@] %~ #@[ - [ #@rplc '';~]
```

In other words: find length of original string, replace the string to be counted with the empty string, find the difference in lengths and divide by the length of the string to be counted.

Example use:

```   'the three truths' countss 'th'
3
'ababababab' countss 'abab'
2
```

## Java

Using regular expression pattern matching

```int countSubstring(String string, String substring) {
substring = Pattern.quote(substring);
Pattern pattern = Pattern.compile(substring);
Matcher matcher = pattern.matcher(string);
int count = 0;
while (matcher.find())
count++;
return count;
}
```

Works with: Java version 1.5+

The "remove and count the difference" method:

```public class CountSubstring {
public static int countSubstring(String subStr, String str){
return (str.length() - str.replace(subStr, "").length()) / subStr.length();
}

public static void main(String[] args){
System.out.println(countSubstring("th", "the three truths"));
System.out.println(countSubstring("abab", "ababababab"));
System.out.println(countSubstring("a*b", "abaabba*bbaba*bbab"));
}
}
```
Output:
```3
2
2```
Works with: Java version 1.5+

The "split and count" method:

```import java.util.regex.Pattern;

public class CountSubstring {
public static int countSubstring(String subStr, String str){
// the result of split() will contain one more element than the delimiter
// the "-1" second argument makes it not discard trailing empty strings
return str.split(Pattern.quote(subStr), -1).length - 1;
}

public static void main(String[] args){
System.out.println(countSubstring("th", "the three truths"));
System.out.println(countSubstring("abab", "ababababab"));
System.out.println(countSubstring("a*b", "abaabba*bbaba*bbab"));
}
}
```
Output:
```3
2
2```

Manual looping

```public class CountSubstring {
public static int countSubstring(String subStr, String str){
int count = 0;
for (int loc = str.indexOf(subStr); loc != -1;
loc = str.indexOf(subStr, loc + subStr.length()))
count++;
return count;
}

public static void main(String[] args){
System.out.println(countSubstring("th", "the three truths"));
System.out.println(countSubstring("abab", "ababababab"));
System.out.println(countSubstring("a*b", "abaabba*bbaba*bbab"));
}
}
```
Output:
```3
2
2```

## JavaScript

Using regexes:

```function countSubstring(str, subStr) {
var matches = str.match(new RegExp(subStr, "g"));
return matches ? matches.length : 0;
}
```

Using 'split' and ES6 notation:

```const countSubString = (str, subStr) => str.split(subStr).length - 1;
```

## jq

Using regexes (available in jq versions after June 19, 2014):

```def countSubstring(sub):
[match(sub; "g")] | length;```

Example:

`"the three truths" | countSubstring("th")`

## Julia

Built-in Function

```matchall(r::Regex, s::String[, overlap::Bool=false]) -> Vector{String}

Return a vector of the matching substrings from eachmatch.
```

Main

```ts = ["the three truths", "ababababab"]
tsub = ["th", "abab"]

println("Test of non-overlapping substring counts.")
for i in 1:length(ts)
print(ts[i], " (", tsub[i], ") => ")
println(length(matchall(Regex(tsub[i]), ts[i])))
end
println()
println("Test of overlapping substring counts.")
for i in 1:length(ts)
print(ts[i], " (", tsub[i], ") => ")
println(length(matchall(Regex(tsub[i]), ts[i], true)))
end
```
Output:
```Test of non-overlapping substring counts.
the three truths (th) => 3
ababababab (abab) => 2

Test of overlapping substring counts.
the three truths (th) => 3
ababababab (abab) => 4
```

## K

The dyadic verb _ss gives the positions of substring y in string x.

```  "the three truths" _ss "th"
0 4 13

#"the three truths" _ss "th"
3

"ababababab" _ss "abab"
0 4

#"ababababab" _ss "abab"
2
```

## Klingphix

```include ..\Utilitys.tlhy

:count %s !s
0 >ps
[ps> 1 + >ps
\$s len nip + snip nip] [\$s find dup] while
drop drop ps>
;

"the three truths" "th" count ?
"ababababab" "abab" count ?

" " input```

Other solution

```include ..\Utilitys.tlhy

:count "- " convert "-" 2 tolist split len nip ;

"the three truths" "th" count ?
"ababababab" "abab" count ?

" " input```
Output:
```3
2```

## Kotlin

```// version 1.0.6

fun countSubstring(s: String, sub: String): Int = s.split(sub).size - 1

fun main(args: Array<String>) {
println(countSubstring("the three truths","th"))
println(countSubstring("ababababab","abab"))
println(countSubstring("",""))
}
```
Output:
```3
2
1
```

## Lambdatalk

```{def countSubstring
{def countSubstring.r
{lambda {:n :i :acc :s}
{if {>= :i :n}
then :acc
else {countSubstring.r :n
{+ :i 1}
{if {W.equal? {W.get :i :s} ⫖}
then {+ :acc 1}
else :acc}
:s} }}}
{lambda {:w :s}
{countSubstring.r {W.length :s} 0 0
{S.replace \s by ⫕ in
{S.replace :w by ⫖ in :s}}}}}
-> countSubstring

{countSubstring th the three truths}
-> 3
{countSubstring ab ababa}
-> 2
{countSubstring aba ababa}
-> 1
```

## langur

```writeln len indices "th", "the three truths"
writeln len indices "abab", "ababababab"```
Output:
```3
2```

## Lasso

```define countSubstring(str::string, substr::string)::integer => {
local(i = 1, foundpos = -1, found = 0)
while(#i < #str->size && #foundpos != 0) => {
protect => {
handle_error => { #foundpos = 0 }
#foundpos = #str->find(#substr, -offset=#i)
}
if(#foundpos > 0) => {
#found += 1
#i = #foundpos + #substr->size
else
#i++
}
}
return #found
}
define countSubstring_bothways(str::string, substr::string)::integer => {
local(found = countSubstring(#str,#substr))
#str->reverse
local(found2 = countSubstring(#str,#substr))
#found > #found2 ? return #found | return #found2
}
countSubstring_bothways('the three truths','th')
//3
countSubstring_bothways('ababababab','abab')
//2
```

## Liberty BASIC

```print countSubstring( "the three truths", "th")
print countSubstring( "ababababab", "abab")
end

function countSubstring( a\$, s\$)
c =0
la =len( a\$)
ls =len( s\$)
for i =1 to la -ls
if mid\$( a\$, i, ls) =s\$ then c =c +1: i =i +ls -1
next i
countSubstring =c
end function```

## Logtalk

Using atoms for string representation:

```:- object(counting).

:- public(count/3).

count(String, SubString, Count) :-
count(String, SubString, 0, Count).

count(String, SubString, Count0, Count) :-
(   sub_atom(String, Before, Length, After, SubString) ->
Count1 is Count0 + 1,
Start is Before + Length,
sub_atom(String, Start, After, 0, Rest),
count(Rest, SubString, Count1, Count)
;   Count is Count0
).

:- end_object.
```
Output:
```| ?- counting::count('the three truths', th, N).
N = 3
yes

| ?- counting::count(ababababab, abab, N).
N = 2
yes
```

## Lua

Solution 1:

```function countSubstring(s1, s2)
return select(2, s1:gsub(s2, ""))
end

print(countSubstring("the three truths", "th"))
print(countSubstring("ababababab", "abab"))
```
```3
2```

Solution 2:

```function countSubstring(s1, s2)
local count = 0
for eachMatch in s1:gmatch(s2) do
count = count + 1
end
return count
end

print(countSubstring("the three truths", "th"))
print(countSubstring("ababababab", "abab"))
```
```3
2```

## MACRO-11

```        .TITLE  CSUBS
.MCALL  .TTYOUT,.EXIT
CSUBS:: JMP     DEMO

; COUNT SUBSTRINGS R1 IN R0
COUNT:  CLR     R2
BR      4\$
1\$:     MOV     R0,R3
MOV     R1,R4
2\$:     CMPB    (R3)+,(R4)+
BEQ     2\$
TSTB    -(R4)
BNE     3\$
INC     R2
DEC     R3
MOV     R3,R0
BR      4\$
3\$:     INC     R0
4\$:     TSTB    (R0)
BNE     1\$
RTS     PC

; TEST EXAMPLES
DEMO:   MOV     #ST1,R0
MOV     #SU1,R1
JSR     PC,1\$
MOV     #ST2,R0
MOV     #SU2,R1
JSR     PC,1\$
.EXIT
1\$:     JSR     PC,COUNT
MOVB    R2,3\$
MOV     #3\$,R2
2\$:     MOVB    (R2)+,R0
.TTYOUT
BNE     2\$
RTS     PC
3\$:     .BYTE   0,15,12,0

ST1:    .ASCIZ  /THE THREE TRUTHS/
SU1:    .ASCIZ  /TH/
ST2:    .ASCIZ  /ABABABABAB/
SU2:    .ASCIZ  /ABAB/
.END    CSUBS```
Output:
```3
2```

## Maple

```f:=proc(s::string,c::string,count::nonnegint) local n;
n:=StringTools:-Search(c,s);
if n>0 then 1+procname(s[n+length(c)..],c,count);
else 0; end if;
end proc:

f("the three truths","th",0);

f("ababababab","abab",0);```
Output:
```                                      3

2
```

## Mathematica / Wolfram Language

```StringPosition["the three truths","th",Overlaps->False]//Length
3
StringPosition["ababababab","abab",Overlaps->False]//Length
2
```

## MATLAB / Octave

```  % Count occurrences of a substring without overlap
length(findstr("ababababab","abab",0))
length(findstr("the three truths","th",0))

% Count occurrences of a substring with overlap
length(findstr("ababababab","abab",1))
```
Output:
```>>   % Count occurrences of a substring without overlap
>>   length(findstr("ababababab","abab",0))
ans =  2
>>   length(findstr("the three truths","th",0))
ans =  3
>>   % Count occurrences of a substring with overlap
>>   length(findstr("ababababab","abab",1))
ans =  4
>> ```

## Maxima

```scount(e, s) := block(
[n: 0, k: 1],
while integerp(k: ssearch(e, s, k)) do (n: n + 1, k: k + 1),
n
)\$

scount("na", "banana");
2
```

## MiniScript

```string.count = function(s)
return self.split(s).len - 1
end function

print "the three truths".count("th")
print "ababababab".count("abab")
```
Output:
```3
2
```

## Mirah

```import java.util.regex.Pattern
import java.util.regex.Matcher

#The "remove and count the difference" method
def count_substring(pattern:string, source:string)
(source.length() - source.replace(pattern, "").length()) / pattern.length()
end

puts count_substring("th", "the three truths")      # ==> 3
puts count_substring("abab", "ababababab")          # ==> 2
puts count_substring("a*b", "abaabba*bbaba*bbab")   # ==> 2

# The "split and count" method
def count_substring2(pattern:string, source:string)
# the result of split() will contain one more element than the delimiter
# the "-1" second argument makes it not discard trailing empty strings
source.split(Pattern.quote(pattern), -1).length - 1
end

puts count_substring2("th", "the three truths")      # ==> 3
puts count_substring2("abab", "ababababab")          # ==> 2
puts count_substring2("a*b", "abaabba*bbaba*bbab")   # ==> 2

# This method does a match and counts how many times it matches
def count_substring3(pattern:string, source:string)
result = 0
Matcher m = Pattern.compile(Pattern.quote(pattern)).matcher(source);
while (m.find())
result = result + 1
end
result
end

puts count_substring3("th", "the three truths")      # ==> 3
puts count_substring3("abab", "ababababab")          # ==> 2
puts count_substring3("a*b", "abaabba*bbaba*bbab")   # ==> 2```

## Miranda

```main :: [sys_message]
main = [Stdout (show (countSubstring "the three truths" "th") ++ "\n"),
Stdout (show (countSubstring "ababababab" "abab") ++ "\n")]

countSubstring :: [*]->[*]->num
countSubstring str ss
= 0, if str = []
= 1 + countSubstring (drop len str) ss, if match
= countSubstring (tl str) ss, otherwise
where len   = #ss
match = take len str = ss```
Output:
```3
2```

## Nanoquery

Translation of: Java
```def countSubstring(str, subStr)
return int((len(str) - len(str.replace(subStr, ""))) / len(subStr))
end```

## Nemerle

Translation of: F#
```using System.Console;

module CountSubStrings
{
CountSubStrings(this text : string, target : string) : int
{
match (target) {
|"" => 0
|_ => (text.Length - text.Replace(target, "").Length) / target.Length
}
}

Main() : void
{
def text1 = "the three truths";
def target1 = "th";
def text2 = "ababababab";
def target2 = "abab";

WriteLine(\$"\$target1 occurs \$(text1.CountSubStrings(target1)) times in \$text1");
WriteLine(\$"\$target2 occurs \$(text2.CountSubStrings(target2)) times in \$text2");
}
}
```
Output:
```th occurs 3 times in the three truths
abab occurs 2 times in ababababab```

## NetRexx

NetRexx provides the string.countstr(needle) built-in function:

```/* NetRexx */
options replace format comments java crossref symbols nobinary

-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method countSubstring(inStr, findStr) public static
return inStr.countstr(findStr)

-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method main(args = String[]) public static
strings = ''
find = 'FIND'
ix = 0
ix = ix + 1; strings[0] = ix; find[0] = ix; strings[ix] = 'the three truths'; strings[ix, find] = 'th'
ix = ix + 1; strings[0] = ix; find[0] = ix; strings[ix] = 'ababababab';       strings[ix, find] = 'abab'

loop ix = 1 to strings[0]
str = strings[ix]
fnd = strings[ix, find]
say 'there are' countSubstring(str, fnd) 'occurences of "'fnd'" in "'str'"'
end ix

return```
Output:
```there are 3 occurences of "th" in "the three truths"
there are 2 occurences of "abab" in "ababababab"
```

## NewLISP

```; file:   stringcount.lsp
; url:    http://rosettacode.org/wiki/Count_occurrences_of_a_substring
; author: oofoe 2012-01-29

; Obvious (and non-destructive...)

; Note that NewLISP performs an /implicit/ slice on a string or list
; with this form "(start# end# stringorlist)". If the end# is omitted,
; the slice will go to the end of the string. This is handy here to
; keep removing the front part of the string as it gets matched.

(define (scount needle haystack)
(let ((h (copy haystack)) ; Copy of haystack string.
(i 0)               ; Cursor.
(c 0))              ; Count of occurences.

(while (setq i (find needle h))
(inc c)
(setq h ((+ i (length needle)) h)))

c))                     ; Return count.

; Tricky -- Uses functionality from replace function to find all
; non-overlapping occurrences, replace them, and return the count of
; items replaced in system variable \$0.

(define (rcount needle haystack)
(replace needle haystack "X") \$0)

; Test

(define (test f needle haystack)
(println "Found " (f needle haystack)
" occurences of '" needle "' in '" haystack "'."))

(dolist (f (list scount rcount))
(test f "glart" "hinkerpop")
(test f "abab"  "ababababab")
(test f "th"    "the three truths")
(println)
)

(exit)
```
Output:
```Found 0 occurences of 'glart' in 'hinkerpop'.
Found 2 occurences of 'abab' in 'ababababab'.
Found 3 occurences of 'th' in 'the three truths'.

Found 0 occurences of 'glart' in 'hinkerpop'.
Found 2 occurences of 'abab' in 'ababababab'.
Found 3 occurences of 'th' in 'the three truths'.
```

## Nim

```import strutils

proc count(s, sub: string): int =
var i = 0
while true:
i = s.find(sub, i)
if i < 0:
break
i += sub.len # i += 1 for overlapping substrings
inc result

echo count("the three truths","th")

echo count("ababababab","abab")
```
Output:
```3
2```

## Objective-C

The "split and count" method:

```@interface NSString (CountSubstrings)
- (NSUInteger)occurrencesOfSubstring:(NSString *)subStr;
@end

@implementation NSString (CountSubstrings)
- (NSUInteger)occurrencesOfSubstring:(NSString *)subStr {
return [[self componentsSeparatedByString:subStr] count] - 1;
}
@end

int main(int argc, const char *argv[]) {
@autoreleasepool {

NSLog(@"%lu", [@"the three truths" occurrencesOfSubstring:@"th"]);
NSLog(@"%lu", [@"ababababab" occurrencesOfSubstring:@"abab"]);
NSLog(@"%lu", [@"abaabba*bbaba*bbab" occurrencesOfSubstring:@"a*b"]);

}
return 0;
}
```
Output:
```3
2
2```

The "remove and count the difference" method:

```@interface NSString (CountSubstrings)
- (NSUInteger)occurrencesOfSubstring:(NSString *)subStr;
@end

@implementation NSString (CountSubstrings)
- (NSUInteger)occurrencesOfSubstring:(NSString *)subStr {
return ([self length] - [[self stringByReplacingOccurrencesOfString:subStr withString:@""] length]) / [subStr length];
}
@end

int main(int argc, const char *argv[]) {
@autoreleasepool {

NSLog(@"%lu", [@"the three truths" occurrencesOfSubstring:@"th"]);
NSLog(@"%lu", [@"ababababab" occurrencesOfSubstring:@"abab"]);
NSLog(@"%lu", [@"abaabba*bbaba*bbab" occurrencesOfSubstring:@"a*b"]);

}
return 0;
}
```
Output:
```3
2
2```

Manual looping:

```@interface NSString (CountSubstrings)
- (NSUInteger)occurrencesOfSubstring:(NSString *)subStr;
@end

@implementation NSString (CountSubstrings)
- (NSUInteger)occurrencesOfSubstring:(NSString *)subStr {
NSUInteger count = 0;
for (NSRange range = [self rangeOfString:subStr]; range.location != NSNotFound;
range.location += range.length,
range = [self rangeOfString:subStr options:0
range:NSMakeRange(range.location, [self length] - range.location)])
count++;
return count;
}
@end

int main(int argc, const char *argv[]) {
@autoreleasepool {

NSLog(@"%lu", [@"the three truths" occurrencesOfSubstring:@"th"]);
NSLog(@"%lu", [@"ababababab" occurrencesOfSubstring:@"abab"]);
NSLog(@"%lu", [@"abaabba*bbaba*bbab" occurrencesOfSubstring:@"a*b"]);

}
return 0;
}
```
Output:
```3
2
2```

## OCaml

```let count_substring str sub =
let sub_len = String.length sub in
let len_diff = (String.length str) - sub_len
and reg = Str.regexp_string sub in
let rec aux i n =
if i > len_diff then n else
try
let pos = Str.search_forward reg str i in
aux (pos + sub_len) (succ n)
with Not_found -> n
in
aux 0 0

let () =
Printf.printf "count 1: %d\n" (count_substring "the three truth" "th");
Printf.printf "count 2: %d\n" (count_substring "ababababab" "abab");
;;
```

## Oforth

```: countSubString(s, sub)
0 1 while(sub swap s indexOfAllFrom dup notNull) [ sub size +  1 under+ ]
drop ;```
Output:
```countSubString("the three truths", "th") println
3
countSubString("ababababab", "abab") println
2
```

## ooRexx

``` bag="the three truths"
x="th"
say left(bag,30) left(x,15) 'found' bag~countstr(x)

bag="ababababab"
x="abab"
say left(bag,30) left(x,15) 'found' bag~countstr(x)

-- can be done caselessly too
bag="abABAbaBab"
x="abab"
say left(bag,30) left(x,15) 'found' bag~caselesscountstr(x)```
Output:
```the three truths               th              found 3
ababababab                     abab            found 2
abABAbaBab                     abab            found 2
```

## PARI/GP

```subvec(v,u)={
my(i=1,s);
while(i+#u<=#v,
for(j=1,#u,
if(v[i+j-1]!=u[j], i++; next(2))
);
s++;
i+=#u
);
s
};
substr(s1,s2)=subvec(Vec(s1),Vec(s2));
substr("the three truths","th")
substr("ababababab","abab")```
Output:
```%1 = 3
%2 = 2```

See Delphi

## Perl

```sub countSubstring {
my \$str = shift;
my \$sub = quotemeta(shift);
my \$count = () = \$str =~ /\$sub/g;
return \$count;
#  or return scalar( () = \$str =~ /\$sub/g );
}

print countSubstring("the three truths","th"), "\n"; # prints "3"
print countSubstring("ababababab","abab"), "\n"; # prints "2"
```

## Phix

```sequence tests = {{"the three truths","th"},
{"ababababab","abab"},
{"ababababab","aba"},
{"ababababab","ab"},
{"ababababab","a"},
{"ababababab",""}}
integer start, count
string test, substring
for i=1 to length(tests) do
start = 1
count = 0
{test, substring} = tests[i]
while 1 do
start = match(substring,test,start)
if start=0 then exit end if
start += length(substring)
count += 1
end while
printf(1,"The string \"%s\" occurs as a non-overlapping substring %d times in \"%s\"\n",{substring,count,test})
end for
```
Output:
```The string "th" occurs as a non-overlapping substring 3 times in "the three truths"
The string "abab" occurs as a non-overlapping substring 2 times in "ababababab"
The string "aba" occurs as a non-overlapping substring 2 times in "ababababab"
The string "ab" occurs as a non-overlapping substring 5 times in "ababababab"
The string "a" occurs as a non-overlapping substring 5 times in "ababababab"
The string "" occurs as a non-overlapping substring 0 times in "ababababab"
```

## PHP

```<?php
echo substr_count("the three truths", "th"), PHP_EOL; // prints "3"
echo substr_count("ababababab", "abab"), PHP_EOL; // prints "2"
```

## Picat

Picat has a predicate for searching for substrings (find/4) but on backtracking (e.g. in a findall/2 wrapper) it yields all overlapping substrings which is not correct in this task.

So we have to roll our own. Here are two versions.

### Recursion

```count_substrings_rec(S, SB) = C =>
count_rec(S,SB,0,C).

count_rec([],_SB,Count,Count).
count_rec(SBRest,SB,Count0,Count) :-
SBRest = SB ++ Rest, % "split" into substring and the rest of the string
count_rec(Rest,SB,Count0+1,Count).
count_rec([T|Rest],SB,Count0,Count) :-
T != SB, % this character is not a substring
count_rec(Rest,SB,Count0,Count).```

### Iterative

Iterative version using find/4 (wrap with once/1 to avoid backtracking).

Translation of: Euphoria
```count_substrings_find(S, SB) = C =>
SLen = S.len,
Count = 0,
From = 1,
while (From <= SLen)
(
once(find(slice(S,From),SB,_From2,To)) ->
Count := Count + 1,
From := From + To
;
From := From + 1
)
end,
C = Count.```

The time differences between these two versions are quite large which is shown in a benchmark of searching the substring "ab" in a string of 100 000 random characters from the set of "abcde":

• count_substrings_rec/2: 0.009s
• count_substrings_find: 0.501s

## PicoLisp

```(de countSubstring (Str Sub)
(let (Cnt 0  H (chop Sub))
(for (S (chop Str)  S  (cdr S))
(inc 'Cnt)
(setq S (map prog2 H S)) ) )
Cnt ) )```

Test:

```: (countSubstring "the three truths" "th")
-> 3

: (countSubstring "ababababab" "abab")
-> 2```

## Pike

```write("%d %d\n",
String.count("the three truths", "th"),
String.count("ababababab", "abab"));
```
Output:
```3 2
```

## PL/I

```cnt: procedure options (main);
declare (i, tally) fixed binary;
declare (text, key) character (100) varying;

get edit (text) (L); put skip data (text);
get edit (key)  (L); put skip data (key);

tally = 0; i = 1;
do until (i = 0);
i = index(text, key, i);
if i > 0 then do; tally = tally + 1; i = i + length(key); end;
end;
put skip list (tally);
end cnt;```

Output for the two specified strings is as expected.

Output:

for the following data

```TEXT='AAAAAAAAAAAAAAA';
KEY='AA';
7
```

## PL/M

```100H:
/* CP/M CALLS */
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; CALL BDOS(0, 0); END EXIT;
PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9, S); END PRINT;

/* PRINT A NUMBER */
PRINT\$NUMBER: PROCEDURE (N);
DECLARE S (8) BYTE INITIAL ('.....',13,10,'\$');
DECLARE (P, N) ADDRESS, C BASED P BYTE;
P = .S(5);
DIGIT:
P = P - 1;
C = N MOD 10 + '0';
N = N / 10;
IF N > 0 THEN GO TO DIGIT;
CALL PRINT(P);
END PRINT\$NUMBER;

/* COUNT OCCURRENCES OF SUBSTRING IN STRING */
DECLARE (STR, MATCH) ADDRESS, C BASED STR BYTE;
DECLARE (SP, MP) ADDRESS, (SC BASED SP, MC BASED MP) BYTE;
COUNT = 0;
DO WHILE C <> '\$';
SP = STR;
MP = MATCH;
DO WHILE SC = MC;
SP = SP + 1;
MP = MP + 1;
END;
IF MC = '\$' THEN DO;
STR = SP;
COUNT = COUNT + 1;
END;
ELSE DO;
STR = STR + 1;
END;
END;
RETURN COUNT;
END COUNT\$SUBSTRING;

CALL PRINT\$NUMBER(COUNT\$SUBSTRING(.'THE THREE TRUTHS\$', .'TH\$')); /* PRINTS 3 */
CALL PRINT\$NUMBER(COUNT\$SUBSTRING(.'ABABABABAB\$', .'ABAB\$')); /* PRINTS 2 */
CALL PRINT\$NUMBER(COUNT\$SUBSTRING(.'CAT\$', .'DOG\$')); /* PRINTS 0 */

CALL EXIT;
EOF```
Output:
```3
2
0```

## PowerBASIC

Works with: PB/Win
Works with: PB/CC

Windows versions of PowerBASIC (at least since PB/Win 7, and possibly earlier) provide the `TALLY` function, which does exactly what this task requires (count non-overlapping substrings).

PB/DOS can use the example under BASIC, above.

Note that while this example is marked as working with PB/Win, the `PRINT` statement would need to be replaced with `MSGBOX`, or output to a file. (PB/Win does not support console output.)

```FUNCTION PBMAIN () AS LONG
PRINT "the three truths, th:", TALLY("the three truths", "th")
PRINT "ababababab, abab:", TALLY("ababababab", "abab")
END FUNCTION```
Output:
```the three truths, th:        3
ababababab, abab:            2
```

## PowerShell

Works with: PowerShell version 4.0
```[regex]::Matches("the three truths", "th").count
```

Output:

```3
```
```[regex]::Matches("ababababab","abab").count
```

Output:

```2
```

## Prolog

Works with: SWI-Prolog version 7

Using SWI-Prolog's string facilities (this solution is very similar to the Logtalk solution that uses sub_atom/5):

```count_substring(String, Sub, Total) :-
count_substring(String, Sub, 0, Total).

count_substring(String, Sub, Count, Total) :-
( substring_rest(String, Sub, Rest)
->
succ(Count, NextCount),
count_substring(Rest, Sub, NextCount, Total)
;
Total = Count
).

substring_rest(String, Sub, Rest) :-
sub_string(String, Before, Length, Remain, Sub),
DropN is Before + Length,
sub_string(String, DropN, Remain, 0, Rest).
```

Usage:

```?- count_substring("the three truths","th",X).
X = 3.

?- count_substring("ababababab","abab",X).
X = 2.
```

### version using DCG

Works with: SWI-Prolog version 7.6.4
```:- system:set_prolog_flag(double_quotes,chars) .

occurrences(TARGETz0,SUBSTRINGz0,COUNT)
:-
prolog:phrase(occurrences(SUBSTRINGz0,0,COUNT),TARGETz0)
.

occurrences("",_,_)
-->
! ,
{ false }
.

occurrences(SUBSTRINGz0,COUNT0,COUNT)
-->
SUBSTRINGz0 ,
! ,
{ COUNT1 is COUNT0 + 1 } ,
occurrences(SUBSTRINGz0,COUNT1,COUNT)
.

occurrences(SUBSTRINGz0,COUNT0,COUNT)
-->
[_] ,
! ,
occurrences(SUBSTRINGz0,COUNT0,COUNT)
.

occurrences(_SUBSTRINGz0_,COUNT,COUNT)
-->
!
.
```
Output:
```/*
?- occurrences("the three truths","th",COUNT) .
COUNT = 3.

?- occurrences("the three truths","",COUNT) .
false .

?- occurrences("ababababab","abab",COUNT) .
COUNT = 2.

?- occurrences("ababababab","",COUNT) .
false .

?-
*/

```

## PureBasic

```a = CountString("the three truths","th")
b = CountString("ababababab","abab")
; a = 3
; b = 2```

## Python

```>>> "the three truths".count("th")
3
>>> "ababababab".count("abab")
2
```

## Quackery

Quackery does not come equipped with a "find substring m within string n" function, but one is defined in The Book of Quackery, as a demonstration of creating a finite state machine in Quackery. It is reproduced here with permission.

```  [ [] 95 times
[ i^ space +
join ] ]         constant is alphabet     (         --> \$       )

[ [ 2dup != while
-1 split drop
swap 1 split
unrot drop again ]
drop size ]                 is overlap      (     [ [ --> n       )

[ temp put [] swap
alphabet witheach
[ over -1 poke
over overlap
dup temp share
= if negate
swap dip join ]
drop temp release ]         is eachend      (     [ n --> [       )

[ [] swap
dup temp put
size times
[ temp share
i 1+ split drop
temp share size eachend
nested swap join ]
temp release ]              is buildfsm     (       \$ --> [       )

[ dup [] = iff -1
else
dup carriage = if
[ drop space ]
space - ]
swap ]                      is nextcharn    (       \$ --> n \$     )

[ swap dup size
swap temp put
swap 0
[ over swap peek
temp take
nextcharn
temp put
dup 0 < iff
[ 2drop 0 ] done
peek
dup 0 < until ]
nip
temp take size - + ]        is usefsm       (     \$ [ --> n       )

[ over size 0 = iff
[ 2drop 0 ]
else
[ swap buildfsm
usefsm ] ]              is find\$        (     \$ \$ --> n       )```

`find\$` builds a finite state machine to search for m, (an O(m³) operation), then uses it to search in n with O(n). Rather than use `find\$`, and repeatedly build the same fsm, we will define a word `findall\$` which returns a nest (i.e. list) of positions of m within n. (It actually returns the positions of the end of the substring, relative to (for the first instance) the start of the string, or (for subsequent instances) the end of the previous instance of the substring.)

```  [ over size 0 = iff
[ 2drop [] ] done
[] unrot
swap buildfsm
[ 2dup usefsm
rot 2dup found while
dip [ over size + ]
dip
[ rot over join
unrot ]
swap split
nip swap again ]
2drop drop ]               is findall\$    (     \$ \$ --> [       )```
Output:

Testing `findall\$` in the Quackery shell.

```O> \$ "th" \$ "the three truths" tuck findall\$
... witheach [ split swap echo\$ cr ]
... echo\$
...
th
e th
ree truth
s
Stack empty.
```

Finally we can use `findall\$` to fulfil the task requirements.

```  [ swap findall\$ size ]        is occurences  (     \$ \$ --> n       )

\$ "the three truths" \$ "th" occurences echo cr
\$ "ababababab" \$ "abab" occurences echo cr```
Output:
```3
2
```

## R

The `fixed` parameter (and, in `stringr`, the function of the same name) is used to specify a search for a fixed string. Otherwise, the search pattern is interpreted as a POSIX regular expression. PCRE is also an option: use the `perl` parameter or function.

```count = function(haystack, needle)
{v = attr(gregexpr(needle, haystack, fixed = T)[[1]], "match.length")
if (identical(v, -1L)) 0 else length(v)}

print(count("hello", "l"))```
Library: stringr
```library(stringr)
print(str_count("hello", fixed("l")))```

## Racket

```(define count-substring
(compose length regexp-match*))
```
```> (count-substring "th" "the three truths")
3
> (count-substring "abab" "ababababab")
2
```

## Raku

(formerly Perl 6)

```sub count-substring(\$big, \$little) { +\$big.comb: / :r \$little / }

say count-substring("the three truths", "th"); # 3
say count-substring("ababababab", "abab");     # 2

say count-substring(123123123, 12);            # 3
```

The :r adverb makes the regex "ratchet forward" and skip any overlapping matches. .comb - when given a Regex as an argument - returns instances of that substring. Also, prefix + forces numeric context in Raku (it's a no-op in Perl 5). For the built in listy types that is the same as calling .elems method. One other style point: we now tend to prefer hyphenated names over camelCase.

## Red

```Red []

count-occurrences: function [string substring] [
length? parse string [collect [some [keep substring to substring]]]
]

test-case-1: "the three truths"
test-case-2: "ababababab"

print [test-case-1 "-" count-occurrences test-case-1 "th"]
print [test-case-2 "-" count-occurrences test-case-2 "abab"]
```
Output:
```the three truths - 3
ababababab - 2
```

## Refal

```\$ENTRY Go {
= <Prout <Count ('th') 'the three truths'>>
<Prout <Count ('abab') 'abababab'>>;
};

Count {
(e.item) e.item e.rest = <+ 1 <Count (e.item) e.rest>>;
(e.item) s.x e.rest = <Count (e.item) e.rest>;
(e.item) = 0;
};```
Output:
```3
2```

## REXX

Some older REXXes don't have the built-in function   countstr,   so one is included within the REXX program as a function.

The   countstr   subroutine (below) mimics the BIF in newer REXXes   (except for error checking).

Either of the first two strings may be null.

The third argument is optional and is the   start position   to start counting   (the default is   1,   meaning the first character).
If specified, it must be a positive integer   (and it may exceed the length of the 1st string).

The third argument was added here to be compatible with the newer REXXes BIF.

No checks are made (in the   countstr   subroutine) for:

•   missing arguments
•   too many arguments
•   if   start   is a positive integer (when specified)
```/*REXX program counts the  occurrences  of a (non─overlapping)  substring  in a string. */
w=.                                                                 /*max. width so far.*/
bag= 'the three truths'    ;      x= "th"       ;        call showResult
bag= 'ababababab'          ;      x= "abab"     ;        call showResult
bag= 'aaaabacad'           ;      x= "aa"       ;        call showResult
bag= 'abaabba*bbaba*bbab'  ;      x= "a*b"      ;        call showResult
bag= 'abaabba*bbaba*bbab'  ;      x= " "        ;        call showResult
bag=                       ;      x= "a"        ;        call showResult
bag=                       ;      x=            ;        call showResult
bag= 'catapultcatalog'     ;      x= "cat"      ;        call showResult
bag= 'aaaaaaaaaaaaaa'      ;      x= "aa"       ;        call showResult
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
countstr:   procedure;  parse arg haystack,needle,start;      if start==''  then start=1
width=length(needle)
do \$=0  until p==0;         p=pos(needle,haystack,start)
start=width + p                    /*prevent overlaps.*/
end   /*\$*/
return \$                                                 /*return the count.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
showResult: if w==. then do;                   w=30        /*W:  largest haystack width.*/
say center('haystack',w)  center('needle',w%2)  center('count',5)
say left('', w, "═")      left('', w%2, "═")    left('', 5, "═")
end

if bag==''  then bag= " (null)"                /*handle displaying of nulls.*/
if   x==''  then   x= " (null)"                /*   "        "      "   "   */
say left(bag, w)           left(x, w%2)            center(countstr(bag, x), 5)
return
```

output   when using the default (internal) inputs:

```           haystack                needle      count
══════════════════════════════ ═══════════════ ═════
the three truths               th                3
ababababab                     abab              2
abaabba*bbaba*bbab             a*b               2
abaabba*bbaba*bbab                               0
(null)                        a                 0
(null)                         (null)           1
catapultcatalog                cat               2
aaaaaaaaaaaaaa                 aa                7
```

## Ring

```aString = "Ring Welcome Ring to the Ring Ring Programming Ring Language Ring"
bString = "Ring"
see count(aString,bString)

func count cString,dString
sum = 0
while substr(cString,dString) > 0
sum++
cString = substr(cString,substr(cString,dString)+len(string(sum)))
end
return sum```

Output:

```6
```

## RPL

Works with: Halcyon Calc version 4.2.7
```≪ DUP SIZE 1 - → str substr subsize
≪ 0
1 str SIZE subsize + FOR j
str j DUP subsize + SUB
IF substr == THEN
1 +
j subsize + 'j' STO
END
NEXT
≫ ≫ 'CNTSUB' STO
```
```"the three truths" CNTSUB
"ababababab" CNTSUB
```
Output:
```2: 3
1: 2
```

## Ruby

```def countSubstrings str, subStr
str.scan(subStr).length
end

p countSubstrings "the three truths", "th"      #=> 3
p countSubstrings "ababababab", "abab"          #=> 2
```

String#scan returns an array of substrings, and Array#length (or Array#size) counts them.

## Run BASIC

```print countSubstring("the three truths","th")
print countSubstring("ababababab","abab")

FUNCTION countSubstring(s\$,find\$)
WHILE instr(s\$,find\$,i) <> 0
countSubstring = countSubstring + 1
i = instr(s\$,find\$,i) + len(find\$)
WEND
END FUNCTION```
Output:
```3
2```

## Rust

```fn main() {
println!("{}","the three truths".matches("th").count());
println!("{}","ababababab".matches("abab").count());
}
```
Output:
```3
2
```

## Scala

### Using Recursion

```import scala.annotation.tailrec
def countSubstring(str1:String, str2:String):Int={
@tailrec def count(pos:Int, c:Int):Int={
val idx=str1 indexOf(str2, pos)
if(idx == -1) c else count(idx+str2.size, c+1)
}
count(0,0)
}
```

### Using Sliding

```def countSubstring(str: String, sub: String): Int =
str.sliding(sub.length).count(_ == sub)
```

### Using Regular Expressions

```def countSubstring( str:String, substr:String ) = substr.r.findAllMatchIn(str).length
```

```println(countSubstring("ababababab", "abab"))
println(countSubstring("the three truths", "th"))
```
Output:
```2
3```

## Scheme

Works with: Gauche Scheme
```gosh> (use gauche.lazy)
#<undef>
gosh> (length (lrxmatch "th" "the three truths"))
3
gosh> (length (lrxmatch "abab" "ababababab"))
2
```

## Seed7

```\$ include "seed7_05.s7i";

const func integer: countSubstring (in string: stri, in string: searched) is func
result
var integer: count is 0;
local
var integer: offset is 0;
begin
offset := pos(stri, searched);
while offset <> 0 do
incr(count);
offset := pos(stri, searched, offset + length(searched));
end while;
end func;

const proc: main is func
begin
writeln(countSubstring("the three truths", "th"));
writeln(countSubstring("ababababab", "abab"));
end func;```
Output:
```3
2
```

## SETL

```program count_overlapping_substrings;
tests := [["the three truths", "th"], ["ababababab", "abab"]];
loop for [s, subs] in tests do
print("'" + subs + "' in '" + s + "': "
+ str countSubs(s, subs));
end loop;

proc countSubs(s, subs);
count := 0;
loop while s(subs) /= om do
s(subs) := "";
count +:= 1;
end loop;
return count;
end proc;
end program;```
Output:
```'th' in 'the three truths': 3
'abab' in 'ababababab': 2```

## SenseTalk

Simply stated:

```put the number of occurrences of "th" in "the three truths" --> 3
put the number of occurrences of "abab" in "ababababab" -- > 2```

User-created function:

```put countSubstring("aaaaa","a") // 5
put countSubstring("abababa","aba") // 2

function countSubstring mainString, subString
return number of occurrences of subString in mainString
end countSubstring```

## Sidef

Built-in:

```say "the three truths".count("th");
say "ababababab".count("abab");
```

User-created function:

```func countSubstring(s, ss) {
var re = Regex.new(ss.escape, 'g');      # 'g' for global
var counter = 0;
while (s =~ re) { ++counter };
return counter;
}

say countSubstring("the three truths","th");
say countSubstring("ababababab","abab");
```
Output:
```3
2
```

## Simula

```BEGIN

INTEGER PROCEDURE COUNTSUBSTRING(T,TSUB); TEXT T,TSUB;
BEGIN
INTEGER N,I;
I := 1;
WHILE I+TSUB.LENGTH-1 <= T.LENGTH DO
IF T.SUB(I,TSUB.LENGTH) = TSUB THEN
BEGIN
N := N+1;
I := I+MAX(TSUB.LENGTH,1);
END ELSE I := I+1;
COUNTSUBSTRING:= N;
END COUNTSUBSTRING;

OUTINT(COUNTSUBSTRING("THE THREE TRUTHS", "TH"),0);
OUTIMAGE;
OUTINT(COUNTSUBSTRING("ABABABABAB", "ABAB"),0);
OUTIMAGE;
END.```
Output:
```3
2
```

## Smalltalk

Works with: Smalltalk/X
```Transcript showCR:('the three truths' occurrencesOfString:'th').
Transcript showCR:('ababababab' occurrencesOfString:'abab')
```
Output:
```3
2```

## SNOBOL4

```        DEFINE("countSubstring(t,s)")

OUTPUT = countSubstring("the three truths","th")
OUTPUT = countSubstring("ababababab","abab")

:(END)
countSubstring t ARB s = :F(RETURN)
countSubstring = countSubstring + 1 :(countSubstring)
END
3
2```

## Standard ML

```fun count_substrings (str, sub) =
let
fun aux (str', count) =
let
val suff = #2 (Substring.position sub str')
in
if Substring.isEmpty suff then
count
else
aux (Substring.triml (size sub) suff, count + 1)
end
in
aux (Substring.full str, 0)
end;

print (Int.toString (count_substrings ("the three truths", "th")) ^ "\n");
print (Int.toString (count_substrings ("ababababab", "abab")) ^ "\n");
print (Int.toString (count_substrings ("abaabba*bbaba*bbab", "a*b")) ^ "\n");
```

## Stata

```function strcount(s, x) {
n = 0
k = 1-(i=strlen(x))
do {
if (k = ustrpos(s, x, k+i)) n++
} while(k)
return(n)
}

strcount("peter piper picked a peck of pickled peppers", "pe")
5

strcount("ababababab","abab")
2```

## Swift

```import Foundation

func countSubstring(str: String, substring: String) -> Int {
return str.components(separatedBy: substring).count - 1
}

print(countSubstring(str: "the three truths", substring: "th"))
print(countSubstring(str: "ababababab", substring: "abab"))```
Output:
```3
2```

## Tcl

The regular expression engine is ideal for this task, especially as the ***= prefix makes it interpret the rest of the argument as a literal string to match:

```proc countSubstrings {haystack needle} {
regexp -all ***=\$needle \$haystack
}
puts [countSubstrings "the three truths" "th"]
puts [countSubstrings "ababababab" "abab"]
puts [countSubstrings "abaabba*bbaba*bbab" "a*b"]```
Output:
```3
2
2```

## Transd

```#lang transd

MainModule: {
countSubstring: (λ s String() sub String()
(with n 0 pl 0
(while (> (= pl (find s sub pl)) -1)
(+= pl (size sub)) (+= n 1))
(lout n))
),
_start: (λ
(countSubstring "the three truths" "th")
(countSubstring "ababababab" "abab")
)
}```
Output:
```3
2
```

## TUSCRIPT

```\$\$ MODE TUSCRIPT, {}
occurences=COUNT ("the three truths",  ":th:")
occurences=COUNT ("ababababab",   ":abab:")
occurences=COUNT ("abaabba*bbaba*bbab",":a\*b:")```
Output:
```3
2
2
```

## TXR

```@(next :args)
@(do (defun count-occurrences (haystack needle)
(for* ((occurrences 0)
(old-pos 0)
(new-pos (search-str haystack needle old-pos nil)))
(new-pos occurrences)
((inc occurrences)
(set old-pos (+ new-pos (length needle)))
(set new-pos (search-str haystack needle old-pos nil))))))
@ndl
@hay
@(output)
@(count-occurrences hay ndl) occurrences(s) of @ndl inside @hay
@(end)```
```\$ ./txr count-occurrences.txr "baba" "babababa"
2 occurence(s) of baba inside babababa
\$ ./txr count-occurrences.txr "cat" "catapultcatalog"
2 occurence(s) of cat inside catapultcatalog```

## UNIX Shell

Works with: Bash
```#!/bin/bash

function countString(){
input=\$1
cnt=0

until [ "\${input/\$2/}" == "\$input" ]; do
input=\${input/\$2/}
let cnt+=1
done
echo \$cnt
}

countString "the three truths" "th"
countString "ababababab" "abab"```
Output:
```3
2```

## VBA

```Function CountStringInString(stLookIn As String, stLookFor As String)
CountStringInString = UBound(Split(stLookIn, stLookFor))
End Function```

## VBScript

user created function

```Function CountSubstring(str,substr)
CountSubstring = 0
For i = 1 To Len(str)
If Len(str) >= Len(substr) Then
If InStr(i,str,substr) Then
CountSubstring = CountSubstring + 1
i = InStr(i,str,substr) + Len(substr) - 1
End If
Else
Exit For
End If
Next
End Function

WScript.StdOut.Write CountSubstring("the three truths","th") & vbCrLf
WScript.StdOut.Write CountSubstring("ababababab","abab") & vbCrLf```

Using built-in Regexp

Run it with CScript.

```function CountSubstring(str,substr)
with new regexp
.pattern=substr
.global=true
set m=.execute(str)
end with
CountSubstring =m.count
end function
WScript.StdOut.Writeline CountSubstring("the three truths","th")
WScript.StdOut.Writeline CountSubstring("ababababab","abab")```
Output:
```3
2
```

## Visual Basic .NET

```Module Count_Occurrences_of_a_Substring
Sub Main()
Console.WriteLine(CountSubstring("the three truths", "th"))
Console.WriteLine(CountSubstring("ababababab", "abab"))
Console.WriteLine(CountSubstring("abaabba*bbaba*bbab", "a*b"))
Console.WriteLine(CountSubstring("abc", ""))
End Sub

Function CountSubstring(str As String, substr As String) As Integer
Dim count As Integer = 0
If (Len(str) > 0) And (Len(substr) > 0) Then
Dim p As Integer = InStr(str, substr)
Do While p <> 0
p = InStr(p + Len(substr), str, substr)
count += 1
Loop
End If
Return count
End Function
End Module```
Output:
```3
2
2
0```

## V (Vlang)

```fn main(){
println('the three truths'.count('th'))
println('ababababab'.count('abab'))
}```
Output:
```3
2
```

## Wortel

```@let {
c &[s t] #!s.match &(t)g

[[
!!c "the three truths" "th"
!!c "ababababab" "abab"
]]
}```

Returns:

`[3 2]`

## Wren

Library: Wren-pattern
Library: Wren-fmt
```import "./pattern" for Pattern
import "./fmt" for Fmt

var countSubstring = Fn.new { |str, sub|
var p = Pattern.new(sub)
return p.findAll(str).count
}

var tests = [
["the three truths", "th"],
["ababababab", "abab"],
["abaabba*bbaba*bbab", "a*b"],
["aaaaaaaaaaaaaa", "aa"],
["aaaaaaaaaaaaaa", "b"],
]

for (test in tests) {
var count = countSubstring.call(test[0], test[1])
Fmt.print("\$6s occurs \$d times in \$q.", Fmt.q(test[1]), count, test[0])
}```
Output:
```  "th" occurs 3 times in "the three truths".
"abab" occurs 2 times in "ababababab".
"a*b" occurs 2 times in "abaabba*bbaba*bbab".
"aa" occurs 7 times in "aaaaaaaaaaaaaa".
"b" occurs 0 times in "aaaaaaaaaaaaaa".
```

Alternatively, using a library method (output same as before):

Library: Wren-str
```import "./str" for Str
import "./fmt" for Fmt

var tests = [
["the three truths", "th"],
["ababababab", "abab"],
["abaabba*bbaba*bbab", "a*b"],
["aaaaaaaaaaaaaa", "aa"],
["aaaaaaaaaaaaaa", "b"],
]

for (test in tests) {
var count = Str.occurs(test[0], test[1])
Fmt.print("\$6s occurs \$d times in \$q.", Fmt.q(test[1]), count, test[0])
}```

## XPL0

```include c:\cxpl\codes;  \intrinsic 'code' declarations
string 0;               \use zero-terminated strings, instead of MSb terminated

func    StrNCmp(A, B, N); \Compare string A to string B up to N bytes long
\This returns:
\       >0 if A > B
\       =0 if A = B
\       <0 if A < B
char    A, B;           \strings to be compared
int     N;              \number of bytes to compare
int     I;
[for I:= 0 to N-1 do
if A(I) # B(I) then
return A(I) - B(I);
return 0;               \they're equal
];      \StrNCmp

func    StrLen(Str);    \Return the number of characters in an ASCIIZ string
char    Str;
int     I;
for I:= 0 to -1>>1-1 do
if Str(I) = 0 then return I;

func    SubStr(A, B);   \Count number of times string B occurs in A
char    A, B;
int     LA, LB, C, I;
[LA:= StrLen(A);  LB:= StrLen(B);
C:= 0;  I:= 0;
while I < LA do
if StrNCmp(B, A+I, LB) = 0 then [C:= C+1;  I:= I+LB]
else I:= I+1;
return C;
];

[IntOut(0, SubStr("the three truths", "th"));  CrLf(0);
IntOut(0, SubStr("ababababab", "abab"));  CrLf(0);
]```
Output:
```3
2
```
```>>   % Count occurrences of a substring without overlap
>>   length(findstr("ababababab","abab",0))
ans =  2
>>   length(findstr("the three truths","th",0))
ans =  3
>>   % Count occurrences of a substring with overlap
>>   length(findstr("ababababab","abab",1))
ans =  4
>>
```

## zkl

Two solutions:

```fcn countSubstring(s,p){ pn:=p.len(); cnt:=n:=0;
while(Void!=(n:=s.find(p,n))){cnt+=1; n+=pn}
cnt
}```
Translation of: J
`fcn countSubstring(s,p){ (pl:=p.len()) and (s.len()-(s-p).len())/pl }`
Output:
```zkl: println(countSubstring("the three truths","th"))
3
zkl: println(countSubstring("ababababab","abab"))
2
zkl: println(countSubstring("ababababab","v"))
0
```

## ZX Spectrum Basic

```10 LET t\$="ABABABABAB": LET p\$="ABAB": GO SUB 1000
20 LET t\$="THE THREE TRUTHS": LET p\$="TH": GO SUB 1000
30 STOP
1000 PRINT t\$: LET c=0
1010 LET lp=LEN p\$
1020 FOR i=1 TO LEN t\$-lp+1
1030 IF (t\$(i TO i+lp-1)=p\$) THEN LET c=c+1: LET i=i+lp-1
1040 NEXT i
1050 PRINT p\$;"=";c''
1060 RETURN```