Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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

share|improve this question
5  
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. –  ProgramFOX Jun 10 at 15:50
1  
Does language's API mean libraries that can be imported (that come with the language) or methods of builtin datatypes or commands themselves? –  Sieg Jun 10 at 15:54
2  
Does it need to deal with strings longer than s for matching? If not: I have a 5 char J solution: +/a=b –  ɐɔıʇǝɥʇuʎs Jun 10 at 15:56
2  
Does input come through variables or STDIN? –  Sieg Jun 10 at 15:58
1  
Function or program? –  Kyle Kanos Jun 10 at 18:08
show 6 more comments

18 Answers 18

up vote 7 down vote accepted

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.
share|improve this answer
    
Impressive.. But I have a small question, did you learn GolfScript just for code golf and solving code problems? –  user19785 Jun 10 at 17:05
1  
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. –  Dennis Jun 10 at 17:09
    
@Dennis [win key] jqt [return] a. [return] is even quicker ;) –  ɐɔıʇǝɥʇuʎs Jun 10 at 17:12
    
@Synthetica: Well, it was just an example. But jqt sounds interesting. What is it? –  Dennis Jun 10 at 17:17
    
@Dennis It's the standard J console that comes with J (it's one of those graphical consoles, like the iPython QTConsole) –  ɐɔıʇǝɥʇuʎs Jun 10 at 17:24
show 3 more comments

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.

share|improve this answer
    
split() isn't part of "your language's API"? –  svidgen Jun 10 at 16:59
2  
it is but its purpose is not to count occurrences of a string... so where is the limit of authorized APIs ? –  Michael Jun 10 at 17:01
1  
@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... –  user19785 Jun 10 at 17:04
    
@404NotFound Good to know ... this is my answer too then? :) ... (+1) –  svidgen Jun 10 at 17:06
1  
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. –  randunel Jun 11 at 21:52
add comment

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
share|improve this answer
    
I thought ababa -> aba was to return 1? –  Kyle Kanos Jun 10 at 18:08
    
@KyleKanos It was, but the author specifically said @Synthetica Absolutley go for it! when I asked him, so I suppose it's okay. –  ɐɔıʇǝɥʇuʎs Jun 10 at 18:09
add comment

C# - 73

//a = "aba";
//b = "ababa";

Console.Write(b.Split(new string[]{a},StringSplitOptions.None).Length-1);

// output = "1"
share|improve this answer
    
It's wrong! aba appears twice in ababa: aba ba ab aba. –  Runemoro Jun 11 at 1:23
2  
@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.. –  malik Jun 11 at 1:25
    
Oh, didn't read... –  Runemoro Jun 11 at 1:26
add comment

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)))
share|improve this answer
    
Worked with every test I put it in... –  user19785 Jun 10 at 16:43
    
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;( ) –  user19785 Jun 10 at 16:44
    
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? –  Sieg Jun 10 at 16:48
    
Yes, absolutely –  user19785 Jun 10 at 16:48
    
Also, it outputs 2 for the a='aba'; b='ababa' case. –  Sieg Jun 10 at 16:50
show 10 more comments

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)

share|improve this answer
add comment

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
$ 
share|improve this answer
add comment

Ruby 2.x

Here goes:

a,b,c=gets,gets.chomp,0;a.size.times{|i|c+=1 if b==a[i...i+b.size]};puts c

Although this answer is longer than some posted already, I believe it remains very true to the author's rules. It prompts the user for two inputs, which makes it an interactive command-line script, and it prints the desired value rather than merely returning it (simply remove the last puts to make it return instead). Additionally, it uses built-in Ruby library functions sparingly. That code would obviously never be found in any Ruby program because...

puts gets.scan(/#{gets.chomp}/).size

...does the trick in far fewer bytes. However, in accordance with the author's rules, I went with the more long-winded option.

Worth noting: with the case of searching "ababa" for "aba", this example yields 2, which indeed goes against what the author said. However, to me it seems that the rule should be to include these cases. The commonly implemented Boyer-Moore and Knuth-Morris-Pratt string search algorithms both take into account this case of overlapping instances.

share|improve this answer
add comment

C# - 66 Bytes

//s = "aba"
//t = "ababa"

Console.Write(t.Split(new[]{s},StringSplitOptions.None).Length-1);

//Output: 1
share|improve this answer
    
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. –  malik Jun 12 at 6:49
    
@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. –  tsavinho Jun 12 at 6:53
1  
Fair enough. I don't mind either way. I was just letting you know. –  malik Jun 12 at 7:18
add comment

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);}
share|improve this answer
add comment

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

share|improve this answer
add comment

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))
share|improve this answer
add comment

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
share|improve this answer
add comment

Mathematica 26 23

Works like Dennis' algorithm, but wordier:

Length@StringCases[a,b]

Three chars shaved off by Szabolics.

share|improve this answer
    
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. –  Szabolcs Jun 11 at 17:53
    
Thanks. I forgot about StringCases. It was unclear to me what the OP meant by the language's API. –  David Carraher Jun 11 at 18:25
    
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. –  Szabolcs Jun 11 at 18:43
add comment

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;
}
share|improve this answer
add comment

Java (38)

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

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

share|improve this answer
add comment

Cobra - 25

print a.split(b).length-1
share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.