时间戳

首页 > 解决方案 > 优化算法以查找字符串的多个特定子字符串

c++ - 优化算法以查找字符串的多个特定子字符串

问题描述

我是 C++ 编码的新手，刚刚开始解决竞争性编程问题。我想解决以下任务：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1620。
我想找到一个字符串的子字符串。问题是下面的代码很慢，我通过“超出时间限制”“错误”导致提交失败。我能做些什么来加快代码速度？

#include <iostream>
#include <sstream>
#include <stdio.h>
#include <string.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    stringstream ss;
    string m;
    char prob[100000];
    char substring[1000];
    int howManyCases = 0;
    int numberOfTests = 0; 

    cin >> numberOfTests;
    cin.ignore();
    while(numberOfTests--)
    {
        cin >> prob >> howManyCases;

        while(howManyCases--)
        {
            cin >> substring;
            if (strstr(prob,substring)) {
                ss << 'y' << "\n";
            }
            else
            {
                ss << 'n' << "\n";
            }
        }
    }

    m = ss.str();
    cout << m;

    return 0;
}

标签： c++optimizationsubstring

解决方案

我会让你成为<algorithm>标题：

std::string parent_string = "some string lala";
std::string sub_string = "lala";
auto found = parent_string.find(sub_string);

它将迭代器返回到子字符串所在的位置。然后我会使用这个子句：

if (found != std::string::npos) std::cout << "y\n";
else std::cout << "n\n";

如果对标准库的使用没有限制，使用它总是比创建自己的算法（可能无法处理一些你不会想到的特殊情况）更好的选择。另外，将那些巨大的丑陋c-style arrays换成std::string.

推荐阅读