默

生存是唯一的长路

发表于 更新于 分类于 阅读次数： Disqus： 本文字数： 17k 阅读时长 ≈ 15 分钟

  • vscode c语言在ubuntu windows下代码提示/补全,简单编译.

  • 更新

    1
    2
    18.03.24 ubuntu下代码提示/补全
    18.10.05 新增win10下配置,补全简单编译.更新版本
阅读全文 »

发表于 分类于 ， 阅读次数： Disqus： 本文字数： 3k 阅读时长 ≈ 3 分钟

  • 记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.

  • 初步涉及KMP时,有些蒙蔽,还好遇到了 阮一峰 的讲解,才啃下来.博文图来自资料链接.

资料来源如下

  • 从头到尾彻底理解KMP（2014年8月22日版）
  • 如何更好的理解和掌握 KMP 算法? - 海纳的回答 - 知乎
  • 字符串匹配的KMP算法 阮一峰

KMP

暴力搜索

  • 搜索字符串时最常用的是暴力搜索,

    • 一个字符一个字符去比较,第一位相同,比较第二位
    • 遇到不同字符,目标字符指针后移一位,重复.
    • 直到遇到模式字符终止符.返回目标字符指针位置.

  • 以下是暴力搜素的C语言一个实现版本

    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 ViolentMatch(char* s, char* p)
    {
      int sLen = strlen(s);
      int pLen = strlen(p);

      int i = 0;
      int j = 0;
      while (i < sLen && j < pLen)
      {
          if (s[i] == p[j])
          {
              //①如果当前字符匹配成功（即S[i] == P[j]），则i++，j +
              i++;
              j++;
          }
          else
          {
              //②如果失配（即S[i]! = P[j]），令i = i - (j - 1) j = 0
              i = i - j + 1;
              j = 0;
          }
      }
      //匹配成功，返回模式串p在文本串s中的位置，否则返回-1
      if (j == pLen)
          return i - j;
      else
          return -1;
    }

  • 对暴力搜索而言,整个流程上改进空间不大,主要集中在当搜索过程.见示例

    • 1
    • 2
    • 3
    • 4

  • 可以看到整个搜索过程,最明显的一个缺陷是,搜索到模式字符串的中间很长一段了,遇到一个坏字符,目标字符串指针移位1.模式字符还是要从头开始比较,模式字符在上一轮坏字符之前的比较相当于白做了.

KMP算法

  • 当空格与D不匹配时，前面六个字符是"ABCDAB"已知。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置" j 移回已经比较过的位置，而是继续把它向后移。

  • 经过KMP处理六个字符已知字符串"ABCDAB"后,可以得到一个表格,对应模式字符串每一位可前移的位数.如图
    8

  • 于是整个过程优化如下.

    • 1
    • 2
    • 3
    • 但空格与D失配,其前一位 (B->2),所以 j=2
    • 5
    • 但空格与C依旧失配.其前一位 (B->0),所以 j=0
    • 6

  • 对应c代码变化如下

    • 最主要的变化是引入next[]数组(方便).

      因为c语言数组元素由0开始,上文的表格右移一位.0位填充-1.得到next数组.

    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 KMP(char * t, char * p)
    {
      int sLen = strlen(s);
      int pLen = strlen(p);

      int i = 0;
      int j = 0;
      while (i < sLen && j < pLen)
      {
        //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
        if (j == -1 || s[i] == p[j])
        {
          i++;
          j++;
        }
        else
        {
          //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
          //next[j]即为j所对应的next值
          j = next[j];
        }
      }
      //匹配成功，返回模式串p在文本串s中的位置，否则返回-1
      if (j == pLen)
          return i - j;
      else
          return -1;
    }

部分匹配表(Partial Match Table),next[]数组

  • 这里大量摘录了如何更好的理解和掌握 KMP 算法? - 海纳的回答 - 知乎的答案.

  • 上文提及的表格即部分匹配表.

  • 字符串的前缀和后缀。

    • 前缀: 如果字符串A和B，存在A=BS，其中S是任意的非空字符串，那就称B为A的前缀。例如，”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}，我们把所有前缀组成的集合，称为字符串的前缀集合。
    • 后缀: 后缀A=SB， 其中S是任意的非空字符串，那就称B为A的后缀，例如，”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，然后把所有后缀组成的集合，称为字符串的后缀集合。
    • 要注意的是，字符串本身并不是自己的后缀。

  • PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度,如图
    前后缀

  • 这里换一组字符串“abababca”说明next数组求法

  • 求next数组的过程完全可以看成字符串匹配的过程，即以模式字符串为主字符串，以模式字符串的前缀为目标字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。

  • 具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行字符串搜索(KMP)。 在任一位置，能匹配的最长长度(j值)就是当前位置的next值。如下图所示。

  • 如图

    • 1
    • 2
    • 3
    • 4
    • 5

  • c语言实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    void GetNext(char* p,int next[])
    {
      int pLen = strlen(p);
      next[0] = -1;
      int k = -1;
      int j = 0;
      while (j < pLen - 1)
      {
        //p[k]表示前缀，p[j]表示后缀
        if (k == -1 || p[j] == p[k])
        {
          ++k;
          ++j;
          next[j] = k;
        }
        else
        {
          k = next[k];
        }
      }
    }

  • 流程(部分):

    • next[6]=4
    • p[6] != p[4]; k = next[4] = 2
    • p[6] != p[2]; k = next[2] = 0
    • p[6] != p[0]; k = next[0] = -1
    • k == -1; ++k; ++j; next[7]=k=0;
    • …

  • 回到字符串"ABCDAB",得到的next数组如下
    next

next[]数组改进

  • 当 j 沿着next[]数组回溯时,可能产生一种情况是:连续几次回溯到的字符相同,即连续几次比较了模式字符串里相同的字符.

  • 如上一节流程部分.

    • p[4] p[2] p[0]都为元素a,实际只需要与 p[6] 比较一次即可.

  • 未避免这种情况,可以对next[]数组回溯链上,连续相同的字符合并,直接取前一个字符对应位置next[]数组的值.由此产生的数组叫nextval数组.

  • c代码实现:

    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
    void GetNextval(char* p,int next[])
    {
      int pLen = strlen(p);
      next[0] = -1;
      int k = -1;
      int j = 0;
      while (j < pLen - 1)
      {
        //p[k]表示前缀，p[j]表示后缀
        if (k == -1 || p[j] == p[k])
        {
          ++k;
          ++j;
          //
          if(p[k]==p[j])
          {
            next[j] = next[k];
          }
          else
          {
            next[j] = k;
          }
        }
        else
        {
          k = next[k];
        }
      }
    }

发表于 分类于 阅读次数： Disqus： 本文字数： 340 阅读时长 ≈ 1 分钟

编程环境

  • Android Studio 3.1.2

问题

  • myprivacy测试中一些应用在进入第二个activity时时常闪退,爆出空对象错误.

    1
    Attempt to invoke interface method 'boolean android.view.inputmethod.InputConnection.finishComposingText()' on a null object reference

  • 但本身Activity跳转之间并没有输入控件.

过程

  • Google到了,类似故障.

    https://github.com/facebook/react-native/issues/18884

解决

  • 关闭 Android Studio的Advanced Profiling即可,非代码错误

备注

  • 无

发表于 分类于 ， 阅读次数： Disqus： 本文字数： 731 阅读时长 ≈ 1 分钟

分析日志

需求

  • 简单分析日志文件中两个时间差.
  • 计算平均值,中位数,方差等.
  • 图形化展示.

分析

  • 用到的功能

    • 系统io,只需要按行读入即可,当然需要指定gbk编码
    • 科学计算的函数库
    • 简单的画图库

  • python库

    • 系统的 io 库即可
    • numpy 库,大材小用
    • matplotlib.pyplot,大材小用

示例

  • 按行读入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    with open(path,encoding='gbk') as f:
      for number, line in enumerate(f):
          #去空格
          line = line.strip().replace(' ','')
          #匹配字符串
          try:
              ln1 = line.index(str1)
          except ValueError as e:
              ln1 = 1

  • 得到一个list 统计

    1
    2
    3
    4
    5
    print("数量",len(time))
    print("平均值",np.mean(time))
    print("最大值",np.max(time))
    print("最小值",np.min(time))
    print("方差",np.var(time))

  • 画图

    1
    2
    3
    4
    5
    6
    7
    #格式化转化为时间
    for ts in x :
      tx.append(datetime.datetime.fromtimestamp(ts/1000))

    plt.plot(tx,time)
    plt.title('len%d, mean%d, max%d, min%d' % (len(time),np.mean(time),np.max(time),np.min(time))) # 添加图形标题
    plt.show()