Check for occurences of string in other string

Question

Challenge

I'm sure you read the title, and came in to farm your rep, thinking its kids' stuff, but think again! You have to challenge each other in the shortest code to count the occurences of a string in another. For example, given the following input:

aaaabbbbsssffhd

as a string, and the string

s

should output

3

Rules

Just before you smile and say, "Hey, I'll use ----," read this:

• No use of external libraries, or your language's API. You have to implement it manually. Which means you can't use your language's built-in function or method for counting occurences
• No file I/O
• No connecting with a server, website, et cetera
• In a case of `ababa`, where it starts with `aba` and if you read the last 3 letters it's also `aba`, you only count one*

Thank you @ProgramFOX for that (the last rule)!
*Hint: When you count occurences, you can remove the ones you counted to avoid disobeying this rule

I think the last 2 rules are just for rule benders!

Winning Criterion

As previously stated the winner is the code with the less bytes used. The winner will be announced five days later (15 June 2014)

My Small Answer

Here's my C++ answer, where it assumes that the li variable holds the string to check occurences in, and l is the string to look for in f:

Ungolfed

int c = 0;
while (li.find(lf) != string::npos)
{
 int p = li.find(lf);
 int l = p + lf.length() - 1;
 for (p = p; p <= l; p++)
 {
 li[p] = static_cast<char>(8);
 }
 ++c;
}

Of course, to use std::string, you have to include the string header file!

Golfed

int c=0;while(li.find(lf)!=string::npos){int p=li.find(lf);int l=p+lf.length()-1;for(p=p;p<=l;p++){li[p]=static_cast<char>(8);}++c;}

Result

The variable c is going to be the value of how many times the string was found

---

Enjoy!

Winner

After a long wait @Dennis answer wins with only 3 bytes, written in GolfScript

• user3094403: Should we count the same character twice? For example, if the input is ababa and aba, should we output 1 or 2? The third a is both the end of the first aba and the begin of the second aba.
• seequ: Does language's API mean libraries that can be imported (that come with the language) or methods of builtin datatypes or commands themselves?
• ɐɔıʇǝɥʇuʎs: Does it need to deal with strings longer than s for matching? If not: I have a 5 char J solution: +/a=b
• seequ: Does input come through variables or STDIN?
• Kyle Kanos: Function or program?

Answer 1

GolfScript, 3 bytes

/,(

Assumes string and substring are on the stack.

Try it online.

How it works

/ # Split the string around occurrences of the substring.
, # Get the length of the split array.
( # Subtract 1.

• user19785: Impressive.. But I have a small question, did you learn GolfScript just for code golf and solving code problems?
• Dennis: I did, but I use it occasionally for other tasks by now. Need an ASCII table? golfscript <<< '127,32,-""+' is faster than opening a web browser.
• ɐɔıʇǝɥʇuʎs: @Dennis [win key] jqt [return] a. [return] is even quicker ;)
• Dennis: @Synthetica: Well, it was just an example. But jqt sounds interesting. What is it?
• ɐɔıʇǝɥʇuʎs: @Dennis It's the standard J console that comes with J (it's one of those graphical consoles, like the iPython QTConsole)

Answer 2

JavaScript 32

Nothing really interesting here...

(p=prompt)().split(p()).length-1

split main purpose is to create an array from a string using the delimiter in argument.

• svidgen: split() isn't part of "your language's API"?
• Michael M.: it is but its purpose is not to count occurrences of a string... so where is the limit of authorized APIs ?
• user19785: @Michael I apologize of being vague, this is acceptable.. I edited the question to rephrase to "you can't use your language's built-in function or method for counting occurences", so if it is not intended for the purpose of the question, you can use it...
• svidgen: @404NotFound Good to know ... this is my answer too then? :) ... (+1)
• randunel: This is the only answer which doesn't assume that the vars have already been initialized, so you've got my upvote. If you assumed the vars were initialized like all the other answers, you would've gotten a.split(b).length-1 19. Maybe @svidgen should clarify initialization in the question.

Answer 3

J (7)

No use of external libraries Check! , or your language's API. Check...? I don't know what an language API is. You have to implement it manually Check! No file I/O Check! No connecting with a server, website, et cetera Check!

+/a E.b

How it works:

E. is WindowedMatch: the J Refsheet gives 're' E. 'reread' as example. This gives 1 0 1 0 0 0. Then, the only thing left to do is simply adding this with +/ (basically sum).

I don't think this counts as using your language's built-in function or method for counting occurences, but that's disputable.

EDIT: Just to be clear:

 +/'aba'E.'ababa'
2

• Kyle Kanos: I thought ababa -> aba was to return 1?
• ɐɔıʇǝɥʇuʎs: @KyleKanos It was, but the author specifically said @Synthetica Absolutley go for it! when I asked him, so I suppose it's okay.

Answer 4

C# - 73

//a = "aba";
//b = "ababa";
Console.Write(b.Split(new string[]{a},StringSplitOptions.None).Length-1);
// output = "1"

• user23125: It's wrong! aba appears twice in ababa: aba ba ab aba.
• mnsr: @Runemoro "In a case of ababa, where it starts with aba and if you read the last 3 letters it's also aba, you only count one*" << In the rules..
• user23125: Oh, didn't read...

Answer 5

Python 2.x - (削除) 49 23 (削除ここまで) 22 bytes

This is assuming variable input is okay. Both strings can be of any length.

Shortened @avall.

a='s'
b='aaaabbbbsssffhd'
print~-len(b.split(a))

49 bytes version, counts every instance of the substring ('aba' is in 'ababa' twice).

a='s'
b='aaaabbbbsssffhd'
print sum(a==b[i:i+len(a)]for i in range(len(b)))

• user19785: Worked with every test I put it in...
• user19785: And language's API means you have to use your own function or method, not use the language's built-in way to do it (if it has one, I'm a C++ programmer;( )
• seequ: Well the second one absolutely is language's own method for it. Also, the first one outputs 3 if a='aa' and b is the same. Is that okay?
• user19785: Yes, absolutely
• seequ: Also, it outputs 2 for the a='aba'; b='ababa' case.

Answer 6

Powershell 32

($args[0]-split$args[1]).count-1

Works like this:

PS C:\MyFolder> .\ocurrences.ps1 ababa aba
1

Explanation: Uses -split to separate the first argument by the second one, returns the size of the array resulting from the split (minus 1)

Answer 7

Applescript, 106 bytes

Applescript is a fun, but silly language to golf in.

on run a
set AppleScript's text item delimiters to (a's item 1)
(count of (a's item 2)'s text items)-1
end

Run with osascript:

$ osascript instr.scpt s aaaabbbbsssffhd
3
$ 

Answer 8

C# - 66 Bytes

//s = "aba"
//t = "ababa"
Console.Write(t.Split(new[]{s},StringSplitOptions.None).Length-1);
//Output: 1

• mnsr: lol. That's basically my answer. Usually on this site, if you cant come up with something different than an existing answer, you can give hints to the existing answer on how to save a few extra bytes.
• tsavinho: @malik Listen, I wasn't able to comment at that time. Otherwise I'd commented on your answer. I'm willing to take my answer down, if you want to.
• mnsr: Fair enough. I don't mind either way. I was just letting you know.

Answer 9

C (削除) 130 (削除ここまで) 120

Note: will probably crash if called with incorrect arguments.

r;main(int c,char**a){char*p=*++a,*q,*t;while(*p){for(q=a[1],t=p;*q&&*q==*t;q++)t++;*q?p++:(p=t,r++);}printf("%d\n",r);}

Ungolfed (kinda):

int main(int argc, char *argv[]) {
 int result = 0;
 char *ptr = argv[1];
 while (*ptr) {
 char *tmp, *tmp2 = ptr;
 // str(n)cmp
 for (tmp = argv[2]; *tmp; tmp++, tmp2++)
 if (*tmp != *tmp2)
 break;
 if (*tmp) {
 ptr++;
 } else {
 result++;
 ptr += tmp;
 }
 }
 printf("%d\n", result);
}

Old version with strstr and strlen: 103

l;main(int c,char**a){char*p=a[1];l=strlen(a[2]);while(c++,p>l)p=strstr(p,a[2])+l;printf("%d\n",c-5);}

Answer 10

Delphi XE3 (113)

Takes 2 strings, removes substring from string and substracts new length from old length followed by a division of the substring length.

function c(a,b:string):integer;begin c:=(Length(a)-Length(StringReplace(a,b,'',[rfReplaceAll])))div Length(b)end;

Testing:

c('aaaabbbbsssffhd','s') = 3
c('aaaabbbbsssffhd','a') = 4
c('ababa','aba') = 1
c('ababa','c') = 0

Answer 11

Lua (48)

So i thought I could just submit another answer, this time in lua. Its very possible this could be improved a lot, im very new to this.

print((a.len(a)-a.len(a.gsub(a,b,"")))/b.len(b))

Answer 12

Fortran 90: 101

Standard abuse of implicit typing, works for any length arrays a and b, though one should expect that len(a) < len(b).

function i();i=0;k=len(trim(b))-1;do j=1,len(trim(a))-k;if(a(j:j+k)==b(1:1+k))i=i+1;enddo;endfunction

This function must be contained within a full program to work. a and b are received from stdin and can be entered either on the same line (either comma or space separated) or on different lines. Compile via gfortran -o main main.f90 and execute as you would any other compiled program.

program main
 character(len=256)::a,b
 read*,a,b
 print*,i()
 contains
 function i()
 i=0
 k=len(trim(b))-1
 do j=1,len(trim(a))-k
 if(a(j:j+k)==b(1:1+k))i=i+1
 end do
 end function
end program main

Tests:

>ababa aba
2

I could make the above return 1 if I add 4 characters (,k+1) for the do loop

> aaaabbbbbsssffhd s
3

Answer 13

Mathematica (削除) 26 (削除ここまで) 23

Works like Dennis' algorithm, but wordier:

Length@StringCases[a,b]

Three chars shaved off by Szabolics.

• Szabolcs: Length@StringCases[a,b] is shorter. This problem is not well specified because if we're not allowed to use StringCount, it's not clear whether any of the other builtin String* functions should be allowed either ... they're all based on the same underlying code.
• DavidC: Thanks. I forgot about StringCases. It was unclear to me what the OP meant by the language's API.
• Szabolcs: Using the new composition operator in Mathematica 10, we could even just write a function as Length@*StringCases. This is shorter than Length@StringCases[##]& if we were to go for just writing a function but not actually apply it to a and b.

Answer 14

C++ 225

int n,k,m;
int main()
{
string s1,s2;
cin>>s1;
cin>>s2;
int x=s1.size(),y=s2.size();
if(x>=y)
{
for(int i=0;i<x;i++)
{
k=0,m=0;
for(int j=0;j<y;j++)
{
if(s2[j]==s1[i+m])
{
 k++,m++;
}
else break;
}
if(k==y)
{
n++;
i+=(y-1);
}
}
}
cout<<n<<endl;
return 0;
}

Answer 15

Java (38)

System.out.print(a.split(b).length-1);

(The question did not require a complete program or function.)

Answer 16

Cobra - 25

print a.split(b).length-1

Answer 17

K/Kona 6

+/y~'x

where x is the string and y the substring. ~ is the negate operator, with ', it is applied to every element in x; it will return 0 if it does not match and 1 if it does match. Since it is applied element-wise, the result of y~'x is a vector, the +/ then sums the result giving the total number of occurrences.

Unfortunately, this method requires that y is only one character, otherwise we will be comparing a multi-character string to a single character string, resulting in a length error.

Answer 18

Pascal, 210 B

In Standard Pascal a string has necessarily a minimum length of two char values.^† Therefore it is not possible to find the count of occurrences of a "string" of length one in another string.

type c=char;z=integer;function f(s:array[m..n:z]of c;t:array[p..q:z]of c):z;var
i,j,a,r:z;begin r:=0;i:=n-q+p;for i:=m to i do begin a:=1;for j:=0 to q-p do
begin a:=a*ord(s[i+j]=t[p+j])end;r:=r+a end;f:=r end;

Antighoulfed:

 function occurrencesCount(
 { In Pascal a string is a `packed array[1..N] of char`, N ≥ 2. }
 sample: packed array[sampleFirst..sampleLast: integer] of char;
 needle: packed array[needleFirst..needleLast: integer] of char
 ): integer;
 var
 sampleIndex, needleOffset, intermediateResult, result: integer;
 begin
 result ≔ 0;
 
 sampleIndex ≔ sampleLast − needleLast + needleFirst;
 for sampleIndex ≔ sampleFirst to sampleIndex do
 begin
 intermediateResult ≔ 1;
 
 for needleOffset ≔ 0 to needleLast − needleFirst do
 begin
 { The product is zero if any factor is zero. }
 intermediateResult ≔ intermediateResult *
 ord(
 sample[sampleIndex + needleOffset]
 =
 needle[needleFirst + needleOffset]
 )
 end;
 
 result ≔ result + intermediateResult
 end;
 { In Pascal the function’s result is defined by assigning a value
 to the implicitly declared variable bearing the function’s name. }
 occurrencesCount ≔ result
 end;

_{^† Extended Pascal allows an empty string (''), too.}