Link

点击打开题目链接

Problem

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Mean

给你两个字符串,找出第二个串在第一个串中出现的位置,找不到返回-1

Analysis

直接暴力匹配即可过,可以以用哈希或者KMP等等。

C++ Code1

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        for(int i = 0; i + m <= n; ++i) {
            if(haystack.substr(i, m) == needle)
                return i;
        }
        return -1;
    }
};

C++ code2

class Solution {
public:
    using ull = unsigned long long;
    int strStr(const string &b, const string &a) {
        const ull base = 100000007;
        if(a.size() > b.size()) return -1;
        ull t = 1, ah = 0, bh = 0;
        for(int i = 0; i < a.size(); ++i) {
            t *= base;
            ah = ah * base + a[i];
            bh = bh * base + b[i];
        }
        for(int i = 0; i + a.size() <= b.size(); ++i) {
            if(ah == bh) return i;
            if(i + a.size() < b.size())
                bh = bh * base + b[i+a.size()] - b[i] * t;
        }
        return -1;
    }
};

 

欢迎留言