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;
}

If you want to achieve this using Regular Expressions, you might take a look at boost.org/doc/libs/1_42_0/libs/regex/doc/html/index.html — ereOn
– ereOn, Commented Mar 29, 2010 at 13:26

Timmmm · Accepted Answer · 2010-10-01 21:04:54Z

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

Find the first instance of "ba" using the standard string searching functions.
In a loop look past this "ba" to see how many of the next N characters are also "ba".
If this sequence is longer than the previously recorded longest sequence, save its length and position.
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;
}

p4bl0 · Accepted Answer · 2010-03-29 12:48:50Z

0

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.

answered Mar 29, 2010 at 12:48

p4bl0

3,9061 gold badge25 silver badges21 bronze badges

Comments

susmits · Accepted Answer · 2010-03-29 12:50:52Z

0

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

answered Mar 29, 2010 at 12:50

susmits

2,2482 gold badges24 silver badges27 bronze badges

1 Comment

Timmmm Over a year ago

That's not the same. I think he wants to find /(ba)*/.

Julio Guerra · Accepted Answer · 2010-03-29 13:07:17Z

0

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.

edited Mar 29, 2010 at 13:07

answered Mar 29, 2010 at 12:39

Julio Guerra

5,7219 gold badges53 silver badges77 bronze badges

4 Comments

anon Over a year ago

How does that solve his problem? Please don't post inks without any textual explanation.

Julio Guerra Over a year ago

He wants to find str2 in str1, so he can use str2.find (str1).

mingos Over a year ago

I disagree with the downvote. The link provided may be left with no textual explanation, but it's what I'd recommend as well as one of the best resources about C++ standard library. In fact, the original poster should have googled for this in the first place.

DaClown Over a year ago

No, he wants to find the string in that str2 is repeated in the most. Like str2+ as regular expression

Vijay · Accepted Answer · 2010-03-29 13:23:55Z

0

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.

answered Mar 29, 2010 at 13:23

Vijay

67.7k94 gold badges238 silver badges327 bronze badges

Collectives™ on Stack Overflow

How to find string in a string

5 Answers 5

Comments

Comments

1 Comment

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

1 Comment

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related