How to find string in a string

Question

I somehow need to find the longest string in other string, so if string1 will be "Alibaba" and string2 will be "ba" , the longest string will be "baba". I have the lengths of strings, but what next ?

char* fun(char* a, char& b) 
{
int length1=0;
int length2=0;
int longer;
int shorter;
char end='\0';

while(a[i] != tmp)
{
    i++;
    length1++;
}

int i=0;
while(b[i] != tmp)
{
    i++;
    length++;
}

if(dlug1 > dlug2){
    longer = length1;
    shorter = length2;
}
else{
    longer = length2;
    shorter = length1;
}

 //logics here
   }

int main()
{
char name1[] = "Alibaba";
char name2[] = "ba";
char &oname = *name2;

cout << fun(name1, oname) << endl;

system("PAUSE");
return 0;
}

Answer 1

http://www.cplusplus.com/reference/string/string/find/

Maybe you made it on purpose, but you should use the std::string class and forget archaic things like char* string representation. It will make you able to use lots of optimized methods, such as string research, etc.

Answer 2

What you want should look like this pseudo-code:

i = j = count = max = 0
while (i < length1 && c = name1[i++]) do
  if (j < length2 && name2[j] == c) then
    j++
  else
    max = (count > max) ? count : max
    count = 0
    j = 0
  end
  if (j == length2) then
    count++
    j = 0
  end
done
max = (count > max) ? count : max
for (i = 0 to max-1 do
  print name2
done

The idea is here but I feel that there could be some cases in which this algorithm won't work (cases with complicated overlap that would require going back in name1). You may want to have a look at the Boyer-Moore algorithm and mix the two to have what you want.

Answer 3

The Algorithms Implementation Wikibook has an implementation of what you want in C++.

Answer 4

why dont you use strstr function provided by C.

const char * strstr ( const char * str1, const char * str2 );
      char * strstr (       char * str1, const char * str2 );
Locate substring

Returns a pointer to the first occurrence of str2 in str1,
or a null pointer if str2 is not part of str1.
The matching process does not include the terminating null-characters.

use the length's now and create a loop and play with the original string anf find the longest string inside.

Answer 5

I suggest you to use string class to do this because it's easier than working with char*.

here is a short (but not the best) solution :

#include <iostream>
#include <string>

using namespace std;

string findlongest(string longerStr, string shorterStr);

int main()
{
    cout << findlongest ("alibaba","ba");
    return 0;
}

string findlongest(string longerStr, string shorterStr)
{
    string strtofind = shorterStr;

    int count = 0;

    while(longerStr.find(strtofind) != string.npos)
    {
        count++;
        strtofind += shorterStr;

    }

    cout << "Found at: " << longerStr.find(strtofind.substr(0,count * shorterStr.length())) << endl;

    return strtofind.substr(0,count * shorterStr.length());
}

I think this helps unless I misunderstood.

Best Regards

Answer 6

Wow lots of bad answers to this question. Here's what your code should do:

1. Find the first instance of "ba" using the standard string searching functions.
2. In a loop look past this "ba" to see how many of the next N characters are also "ba".
3. If this sequence is longer than the previously recorded longest sequence, save its length and position.
4. Find the next instance of "ba" after the last one.

Here's the code (not tested):

string FindLongestRepeatedSubstring(string longString, string shortString)
{
    // The number of repetitions in our longest string.
    int maxRepetitions = 0;

    int n = shortString.length(); // For brevity.

    // Where we are currently looking.
    int pos = 0;
    while ((pos = longString.find(shortString, pos)) != string::npos)
    {
        // Ok we found the start of a repeated substring. See how many repetitions there are.
        int repetitions = 1;
        // This is a little bit complicated.
        // First go past the "ba" we have already found (pos += n)
        // Then see if there is still enough space in the string for there to be another "ba"
        // Finally see if it *is* "ba"
        for (pos += n; pos+n < longString.length() && longString.substr(pos, n) == shortString; pos += n)
            ++repetitions;
        // See if this sequence is longer than our previous best.
        if (repetitions > maxRepetitions)
            maxRepetitions = repetitions;
    }
    // Construct the string to return. You really probably want to return its position, or maybe
    // just maxRepetitions.
    string ret;
    while (maxRepetitions--)
        ret += shortString;
    return ret;
}