LeetCode 28. 找出字符串中第一个匹配项的下标 -- 字符串编码成数字匹配

28. 找出字符串中第一个匹配项的下标
    中等
    1.6K
    相关企业
    给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = “sadbutsad”, needle = “sad”
输出：0
解释：“sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：

输入：haystack = “leetcode”, needle = “leeto”
输出：-1
解释：“leeto” 没有在 “leetcode” 中出现，所以返回 -1 。

提示：

1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成

题解

这种类型的题目很常见，标准算法应该是KMP匹配，但是KMP代码太长了，换个简单轻松点的，直接把字符串编码成数字匹配即可。

AC代码

class Solution {
public:
    typedef long long ll;
    ll mod = 1e14+7;
    int strStr(string haystack, string needle) 
    {
        int n = needle.length();
        ll sum = 0;
        ll base = 1;
        for(int i=n-1;i>=0;i--)
        {
            sum += (haystack[i]-'a') * base;
            base *= 26;
            sum %= mod;
            base %= mod;
        }
        ll sum1 = 0;
        base = 1;
        for(int i=n-1;i>=0;i--)
        {
            sum1 += (needle[i]-'a')*base;
            base *= 26;
            sum1 %= mod;
            base %= mod;
        }
        base = 1;
        for(int i=1;i<n;i++)
        {
            base *= 26;
            base %= mod;
        }
        if(sum1 == sum)
            return 0;
        for(int i=n;i<haystack.length();i++)
        {
            sum = sum + mod - (haystack[i-n]-'a')*base;
            sum *= 26;
            sum += haystack[i]-'a';
            sum = (sum + mod)%mod;
            if(sum == sum1)
            return i-n+1;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45