如何在字符串中找到字符串

Question

我需要在其他字符串中找到最长的字符串，所以如果string1是“Alibaba”，string2是“ba”，最长的字符串将是“baba”。我有长度的字符串，但接下来呢？

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

哇这个问题很多不好的答案。以下是您的代码应该执行的操作：

1. 使用标准字符串搜索函数查找“ba”的第一个实例。
2. 在一个循环中，通过这个“ba”来查看接下来的N个字符中有多少个也是“ba”。
3. 如果此序列比先前记录的最长序列长，请保存其长度和位置。
4. 找到最后一个“ba”的下一个实例。

下面的代码（未测试）：

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

Answer 2

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

也许你做是故意的，但你应该使用std :: string类，而忘记类似的char *字符串表示过时的东西。 它将使您能够使用大量的优化方法，如字符串研究等

Answer 3

你想应该是这样的伪代码是什么：

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 

的想法是在这里，但我觉得，可能会出现这种算法无法运行的情况（复杂重叠的情况下需要返回name1）。你可能想看一下Boyer-Moore算法，并将这两种算法混合在一起得到你想要的。

Answer 4

Algorithms Implementation Wikibook在C++中实现了你想要的。

Answer 5

你为什么不使用由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. 

提供功能的strstr使用长度是现在创建一个循环并播放原始字符串ANF发现里面最长的字符串。