leetcode 28 实现 strStr() 后缀数组

缘起

【1】中想校验一下我的后缀数组的板子的愿望再次落空——被T掉了，不论是dc3还是da（da的性能更差）. 其实并不难想象——因为da是nlogn的算法，一旦字符串的规模达到了1e6, 则nlogn将达到恐怖的2000w! 而dc3即便是线性算法（在1e6级别上的表现远优于da）, 但是【2】中说了，它的常数较大. 算法的复杂度依旧不低. 所以基本可以断言, 在精确匹配问题上, kmp、bm、karp-rabin等算法是远胜于后缀数组、后缀树算法的. 毕竟后者还要先针对文本串（文本串的长度一般远大于模式串）构建一个东西，而kmp是针对模式串构造一个东西（kmp复杂度为O(n+m), 而且常数几乎为1），这复杂度当然不可同日而语~ 但是我还是不甘心——因为还是要试一下我的板子对不对啊~ 于是找到”比较弱”的leetcode. 打算找上面一道题目来验证一把我的后缀数组板子的正确性. leetcode 28 实现 strStr()

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

直接套用【1】的板子，不写注释了，注释参考【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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
class Solution {
public:
	int strStr(string haystack, string needle) {
		if (!haystack.length() && needle.length())
		{
			return -1;
		}
		if (!needle.length() || !haystack.length())
		{
			return 0;
		}
		memcpy(pp, needle.c_str(), needle.length()*sizeof(char));
		pp[needle.length()] = 0;
		memcpy(s, haystack.c_str(), haystack.length()*sizeof(char));
		s[haystack.length()] = 0;
		n = 0;
		while(s[n])
		{
			r[n] = s[n]-'a'+1;
			n++;
		}
		r[n]=0;
		dc3(r,sa,n+1,27);
		int lo = kk(false), hi = kk(true), ans = 0x3f3f3f3f;
		if (!hi)
		{
			return -1;
		}
		for (int i = lo; i<=hi; i++) // 符合条件的是sa[lo,...,hi]中的后缀, 找出最小的就是答案
		{
			ans = min(ans, sa[i]);
		}
		return ans;
	}

	static const int maxs=1e5+5, maxp = 1e5+5;
	char s[maxs],pp[maxp];
	int n, sa[maxs*3], r[maxs*3], wa[maxs*3], wb[maxs*3], wv[maxs*3], wss[maxs*3];

	void sort(int *r, int *a, int *b, int n, int m)
	{
		for (int i = 0;i<n; i++)
		{
			wv[i] = r[a[i]];
		}
		for (int i = 0;i<m;i++)
		{
			wss[i] = 0;
		} 
		for (int i =0; i<n; i++)
		{
			wss[wv[i]]++;
		}
		for (int i = 1;i<m;i++)
		{
			wss[i]+=wss[i-1];
		}
		for (int i = n-1; ~i; i--)
		{
			b[--wss[wv[i]]]=a[i];
		} 
	}

	int c0(int *r, int a, int b)
	{
		return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
	}

	bool c12(int k, int *r, int a, int b)
	{
		if (k==2) 
		{
			return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
		}
		else 
		{
			return r[a]<r[b]||r[a]==r[b] && wv[a+1]<wv[b+1];
		}
	}

	void dc3(int *r, int *sa, int n, int m)
	{
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
		int *rn = r+n, *san = sa+n, ta = 0, tb = (n+1)/3, tbc=0, p; 
		r[n] = r[n+1] =0;
		for (int i=0; i<n; i++) 
		{
			if (i%3!=0)
			{
				wa[tbc++] = i;
			}
		} 
		sort(r+2, wa, wb, tbc, m);
		sort(r+1, wb,wa, tbc, m);
		sort(r, wa,wb,tbc, m);
		rn[F(wb[0])]=0; p=1; 
		for (int i = 1; i<tbc; i++)
		{
			rn[F(wb[i])] = c0(r, wb[i-1], wb[i])?p-1:p++;
		} 
		if (p<tbc)
		{
			dc3(rn, san, tbc, p); 
		} 
		else 
		{
			for (int i =0 ; i<tbc; i++)
			{
				san[rn[i]] = i;
			}
		}
		for (int i = 0; i<tbc; i++)
		{
			if (san[i]<tb)
			{
				wb[ta++] = san[i]*3;
			}
		} 
		if (n%3==1) 
		{
			wb[ta++] = n-1;
		}
		sort(r,wb,wa,ta,m);
		for (int i =0;i<tbc; i++)
		{
			wv[wb[i]=G(san[i])] = i; 
		} 
		int i=0,j=0;
		for (p=0; i<ta && j<tbc; p++) 
		{
			sa[p] = c12(wb[j]%3, r, wa[i], wb[j])?wa[i++]:wb[j++]; 
		}
		while (i<ta)
		{
			sa[p++]=wa[i++];
		}
		while(j<tbc)
		{
			sa[p++]=wb[j++];
		}
#undef F(x)
#undef G(x)
	}

	int ck(int x) 
	{
		int i = sa[x], j = 0;
		for (; pp[j];i++,j++)
		{
			if (s[i]!=pp[j])
			{
				return s[i]>pp[j]?1:-1;
			}
		}
		return 0;
	}

	int kk(bool flag)
	{
		int lo = 1, hi = n, ans = 0, mid;
		while(lo<=hi)
		{
			mid = lo+hi>>1;
			int check = ck(mid);
			if (!check)
			{
				ans = mid;
				flag?lo = mid+1:hi = mid-1;
			}
			else
			{
				if (check==1) 
				{
					hi = mid-1;
				}
				else
				{
					lo = mid+1;
				}
			}
		}
		return ans;
	}
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
40 ms
, 在所有 C++ 提交中击败了
9.96%
的用户
内存消耗 :
16.4 MB
, 在所有 C++ 提交中击败了
5.00%
的用户

蜜汁尴尬~ 看来后缀数组哪怕是 dc3 也是慢~ 精确匹配和kmp比不了~

da就不刷了, da将在别的题目中证明其正确性. 因为da用leetcode恶心的class Solution中不能自定义数组sort

参考

【1】https://yfsyfs.github.io/2019/10/10/poj-3461-Oulipo-%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84/

【2】https://yfsyfs.github.io/2019/10/07/%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84%E5%AD%A6%E4%B9%A0/