計算字串中子字串的重疊出現次數

#include<iostream>
using namespace std;
int main ()
{
    int z=0;
    int count=0;
    int set=0;
    string str1="lol";
    string str2;
    cin>>str2;
    for(int x=0;x<str2.size();x  )
    {
        if(str1[z]==str2[x])
        {
            z  ;
            count  ;
            if(count==3)
                {
                    x--;
                    set  ;
                    z=0;
                    count=0;
                }
                else
                continue;
        }
         else
                continue;
        
    }
    cout<<set;

    return 0;
}

在這個問題中，你應該在字串 S 中列印一些“lol”。

僅輸入字串 S (1<=|s|<=105)。

輸出字串 S 中“lol”的列印次數。

例子

input
lolol
output
2

input
llpol
output
0

input
lloll
output
1

我在測驗用例 2 中遇到問題，因為它給了我 1 但輸出應該為零我應該使用什么條件來使這不會發生但不使用任何內置函式？

uj5u.com熱心網友回復：

count1如果您傳遞字符指標或 C 字串，下面的實作將避免創建 std::string。

第二種實作count2可能更有效。

#include <iostream>
#include <cstdint>
#include<iostream>

std::size_t count1( const std::string_view& needle, const std::string_view& haystack ) 
{
    std::size_t count = 0;
    std::size_t n  = needle.size();    
    for ( std::size_t j=0; j<haystack.size()-n 1;   j ) {
        if ( haystack.substr(j,n)==needle ) {
            count  = 1;
        }
    }
    return count;
}

std::size_t count2( const std::string_view& needle, const std::string_view& haystack ) {
    std::size_t count =0;
    std:size_t pos = haystack.find( needle, 0 );
    while ( pos != std::string_view::npos ) {
        count  = 1;
        pos = haystack.find( needle, pos 1 );
    } 
    return count;
}

int main ( int argc, char* argv[] )
{
    std::cout << "Count:" << count1( "lol", argv[1] ) << std::endl;
    return 0;
}

代碼：https : //godbolt.org/z/9GG1TPcaM

Input:
llpol
Output:
0

uj5u.com熱心網友回復：

我在對您的問題的評論（第三條評論）中很早就回答了您可以使用該方法將“lol”與要評估的大字串的子字串進行比較。使用“substr”函式。

其他人提出了“查找”功能。然后你在第 5 條評論中說：

這個任務不使用任何內置函式@JohnnyMopp 抱歉，我應該在我的問題中說明這一點

那么，我們應該使用完全手工制作的所謂“天真的滑動視窗”方法。這很容易理解，并且對于您的用例來說完全足夠了。

我將首先給出詳細的解釋，然后以簡單的編程風格以簡單的方法實作這個想法。

它將在不使用任何內置函式的情況下作業，因此它將完全基于標準指令。

這是如何運作的？

您遍歷搜索字串，然后在其上移動一個滑動視窗。視窗長度是要找到的字串的大小。

通常，視窗將簡單地由一個substr函式定義，但是，因為你說你不想擁有一個函式，我們將使用第二個回圈。這不會以任何明顯的方式減慢您的程式。

例子：

str2             abclololdef
window           | |
window content   abc           Now compare window with str1

slide 1 to the right:

str2             abclololdef
window            | |
window content    bcl       Now compare window with str1

slide 1 to the right:

str2             abclololdef
window             | |
window content     clo       Now compare window with str1

slide 1 to the right:

str2             abclololdef
window              | |
window content      lol       Now compare window with str1. Found. Increment counter

slide 1 to the right:

str2             abclololdef
window               | |
window content       olo       Now compare window with str1


slide 1 to the right:

str2             abclololdef
window                | |
window content        lol       Now compare window with str1. Found. Increment counter

slide 1 to the right:

str2             abclololdef
window                 | |
window content         old       Now compare window with str1. 

slide 1 to the right:

str2             abclololdef
window                  | |
window content          lde       Now compare window with str1. 

slide 1 to the right:

str2             abclololdef
window                   | |
window content           def       Now compare window with str1. 

Now, window is at end. Stop sliding.

你看。有一個視窗。視窗有一個開始位置和一個寬度（str1的大小）和一個結束位置，即“開始位置 寬度”

必須小心，不要將視窗滑過 str1 的右邊界。

為了進行比較，我們將“lol”的位置 0 與 str2[startIndex] 進行比較，然后將“lol”的位置 1 與 str2[startIndex 1] 進行比較，將“lol”的位置 2 與 str2[startIndex 2] 進行比較。這將在一個小回圈中完成。

這可以從 1 到 1 轉換為代碼：

#include <iostream>
#include <string>

int main() {
    // This is the string that we are looking for
    std::string stringToFind = "lol";

    // Get string to evaluate from user
    std::string stringToEvaluate{};
    std::cin >> stringToEvaluate;

    // The width of length of the window
    int width = stringToFind.length();

    // Here we will store the number of times we find "lol"
    int counter = 0;

    // Now iterate over the complete input string. Do NOT cross boundaries
    for (int k = 0; k < stringToEvaluate.length() - width;   k) {

        // Define the sliding window position
        int startPosition = k;
        int endPosition = k   width;
        int windowIndex = 0;

        //Here we will store, if we have a full OK comparison; Assum OK in the beginning
        bool allEqual = true;

        // Now compare the window ketter with the lol string
        for (int windowPositionIndex = startPosition; windowPositionIndex < endPosition;   windowPositionIndex) {
            
            // Compare window with base string
            if (stringToEvaluate[windowPositionIndex] != stringToFind[windowIndex]) {
                allEqual = false;
                break;

            }
            // Next letter of the search string
              windowIndex;
        }
        if (allEqual)   counter;
    }
    std::cout << counter << '\n';
}

由于超簡單的編程風格，創建了許多帶有“說話”名稱的中間變數并撰寫了許多注釋，這應該是可以理解的（我希望）

編輯

我在評論中看到人們在討論速度和大 O 符號。我們可以使用復雜度為 O(n m) 的 KMP。

我可以用 O(n-3) 展示一個更快的解決方案，并且在執行期間我仍然可以作業而不使用任何內置函式。

The idea is taken from Rabin-Karp. But, we can observe that we do not need to calculate hash values. We can directly convert a 3byte string to an 32bit unsigned integer. And then make comparisons on integer basis. Mening, we will treat the string as an overlapping integer array. So, we will first create a compile time constant hash value for the string "lol" (7106412) and then do the complete comparison with the string "lol" with one "cmp edx, 7106412" assembler instruction.

We take also advantage of the fact that std::string will be 0-terminated since C 11.

This will result in compact code (6 statements in main, inclusive output), outperforms everthing else in regards to speed and still works without using any built in function or library.

#include <iostream>
#include <string>

// Hash for the string that we are looking for
constexpr unsigned int hash = ('l' << 16)   ('o' << 8)   'l';
// or: const unsigned int hash = *reinterpret_cast<const unsigned int*>("lol");

int main() {

    // Take any test string to evaluate
    std::string stringToEvaluate{ "aaaaalololbbbbbllpolcccccllollddddd" };

    // Here we will store the number of times we find "lol"
    unsigned int counter = 0;

    // Now iterate over the input string. Do not cross boundaries
    for (size_t k = 0; k < stringToEvaluate.length() - 3;   k) {

        // Compare hash values
        if (hash == (*reinterpret_cast<unsigned int*>(&stringToEvaluate[k])) >> 8)
              counter;
    }
    std::cout << counter << '\n';
}

使用 Microsoft Visual Studio Community 2019 版本 16.11.0 和 gcc11.2 以及帶有“-O3 -Werror -Wall -Wpedantic”的 Clang13 編譯和測驗

標籤：C 细绳 算法

上一篇：尋找有效的子串

下一篇：map[complement]===undefinedvs!map[complement]