每日看病毒分析和leetcode-2

php源码解密

https://www.52pojie.cn/thread-693641-1-1.html

先安装xdebug、vscode的PHP debug插件

https://github.com/nikic/PHP-Parser 使用这个格式化

然后单步调试，过掉反调试，一直到eval就可以看到源码

leetcode 实现strstr

KMP算法一直没看懂，这次看看

前缀函数$\pi(i)$表示$s[0:i]$最长相等的真前缀和真后缀

对于字符串aabaaab

  • $\pi(0)=0$，因为a没有真前缀和真后缀
  • $\pi(1)=1$，因为aa最长相等真前缀和真后缀长度为1
  • $\pi(2)=0$，因为aab没有对应的真前缀和真后缀
  • $\pi(3)=1$，因为aaba最长相等真前缀和真后缀长度为1
  • $\pi(4)=2$
  • $\pi(5)=2$
  • $\pi(6)=3$

KMP算法是严格$O(m)$的，靠的就是前缀函数的几个性质

  1. $\pi(i)\le\pi(i-1)+1$，直观地想，增加了一个字符之后最多增加一个真前缀和真后缀的相等的字符

    • 根据$\pi(i)$定义得到$\s[0:\pi(i)-1]=s[i-\pi(i)+1:i]$，即$\pi(i)$长度的真前缀和真后缀相等
    • 两区间的右端点同时左移，得到$s[0:\pi(i)-2]=s[i-\pi(i)+1:i-1]$，即真前缀和真后缀各减少一个字符
    • 根据$\pi(i-1)$定义得$\pi(i-1)\ge\pi(i)-1$，如果$\pi(i)\ne0$，那么最后一个字符肯定和真前缀地某个字符相等，删掉之后$\pi$函数肯定要减1

  2. 如果$s[i]=s[\pi(i-1)]$，那么$\pi(i)=\pi(i-1)+1$，直观地想，这分别是是$\pi(i-1)$的真后缀的下一个字符，所以成立

    • 根据$\pi(i-1)$定义得到，$s[0:\pi(i-1)-1]=s[i-\pi(i-1):i-1]$，就是1第一个式子带入$i-1$（1）
    • 因为$s[\pi(i-1)]=s[i]$，可得$s[0:\pi(i-1)]=s[i-\pi(i-1):i]$，真前缀和真后缀各增加一个相等字符
    • 根据$\pi(i)$定义得$\pi(i)\ge\pi(i-1)+1$，即有相等的之后真前缀和真后缀相等长度可能增加，结合第一个性质得到$\pi(i)=\pi(i-1)+1$

这样就可以根据这两个性质求出$\pi(i)$，找到最大的$j$，满足$s[0:j-1]=s[i-j:i-1]$，且$s[i]=s[j]$，就得到$\pi(i)=j+1$

  1. 要求$j$尽可能大
  2. 要求$j$满足$s[i]=s[j]$

当$s[\pi(i-1)]\ne s[i]$时，$\pi(i)\le\pi(i-1)$，因为$j=\pi(i)-1$，所以$j\lt\pi(i)-1$，于是可以取（1）式两字串的长度为j的后缀，它们依然是相等的：$s[\pi(i-1)-j:\pi(i-1)-1]=s[i-j:i-1]$

实际上是一个有限状态自动机

接收到一个字符之后，如果和当前字符相等，就进入下一个字符的匹配，如果不相等，则依据当前状态和输入字符判断下一个状态是哪个，最终是一个有限状态自动机。

设要匹配的字符串为pat，原字符串为txt

构造状态转移矩阵dp，如果字符等于pat[j]，则转移到下一个状态，否则就回退到和自己相同的最长前缀。

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
int strStr(char * haystack, char * needle){
    int dp[40000][128];
	memset(dp,0,40000*128*sizeof(int));
	size_t xlen=strlen(haystack);
	size_t ylen=strlen(needle);
	if(ylen==0)return 0;
	int x=0; // 影子状态
	dp[0][needle[0]]=1;
	for(size_t i=1;i<ylen;i++){
		for(char c=0;c<127;c++){
			if(c==needle[i]){
				dp[i][c]=i+1;
			}else{
				dp[i][c]=dp[x][c];
			}
		}
		x=dp[x][needle[i]]; // 这里可以判断x和当前字符是否有最大前缀
	}
	int state=0;
	for(size_t i=0;i<xlen;i++){
		state=dp[state][haystack[i]];
		// printf("%d\n",state);
		if(state==ylen){
			return i-ylen+1;
		}
	}
	return -1;
}

参考：

题解

https://zhuanlan.zhihu.com/p/83334559