首页 > 试题广场 >

substring

[编程题]substring

热度指数：66 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

判断一个string是否是另一个string的子串是一个普遍且重要的问题。现在你也要来解决一个关于子串的小问题。我们现在有一个数量不是很大的string库(0<N <= 500)，并且每个string(1<=len <= 20)都不是很长。对给定的string（0<M <= 1000），你要写一个程序算出它是库中多少个string的子串。

输入描述:

有多个case, 每个case第一行是一个正整数N,之后N行每行一个string,代表string库, 每个string由a-z 26个小写字母组成,然后是一个正整数M，之后M行每行一个string代表你所要询问的string。

输出描述:

每个case输出M行，每行一个正整数，代表当前询问的string是库中多少个string的子串

示例1

输入

3
aaa
aaa
baa
2
aa
ba
1
a
1
a

输出

3
1
1

算法知识视频讲解

羽墨如歌

啊！！我的天，本身是道简单的题目，java就更简单了，哇！我只想说认真独读题！！

好吧！多个case！！给代码

package main;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        //-------------敲重点-------------
        while(input.hasNext()){
        //-------------往上看-------------
            int N = input.nextInt();
            ArrayList<String> lib = new ArrayList<>();
            for (int i = 0; i < N; i++){
                lib.add(input.next());
            }
            int M = input.nextInt();
            ArrayList<String> res = new ArrayList<>();
            for (int i = 0; i < M; i++){
                String str = input.next();
                res.add(str);
            }
            for (int i = 0; i < res.size(); i++){
                int num = 0;
                for (int j = 0; j < lib.size(); j++){
                    if(lib.get(j).contains(res.get(i))){
                        num++;
                    }
                }
                System.out.println(num);
            }
        }
    }
}

发表于 2018-07-12 10:46:58 回复(1)

牛客6481049号

#include <string>
#include <vector>
#include <iostream>

using namespace std;

inline int getResult(const vector<string>& vec, const string& str) {
    int count = 0;
    for(const auto& it : vec) {
        if(it.find(str) != string::npos)
            ++count;
    }
    return count;
}

int main() {
    int N = 0;
    while(cin >> N) {
        vector<string> vec;
        vec.reserve(N);
        for(int i = 0; i < N; ++i) {
            string str;
            cin>>str;
            vec.push_back(str);
        }
        
        int M = 0;
        cin>>M;
        for(int i = 0; i < M;++i) {
            string str;
            cin>>str;
            auto res = getResult(vec,str);
            cout<<res<<endl;
        }
    }
    return 0;
}

发表于 2018-10-01 10:52:46 回复(0)