Search code examples
algorithmdivide-and-conquer

and conquer algorithm - search for pattern in string

I am trying to write a divide divide-and-conquer algorithm in pseudocode that finds how many occurrences of a 3-letter pattern there are in a given string of n letters.

Something like this in pseudocode:

the pattern is fixed: XXY

int searchString("CDSXXYZSE")  
    .  
    .  
    search for "XXY"  
    .  
    .  
return (1)

Or 

int searchString("CDSXZXYZSE")  
    .  
    .  
    search for "XXY"  
    .  
    .  
return (0)

Thank you all for your time!

Solution

  • in the divide step i would split up your string parameter into all possible 3-letter combinations, in your example (CDS, DSX, XXY ...). Then test equality to the searched pattern and add up the number of matches in the conquer step.