0°

面试算法知识梳理三:字符串算法第二部分

内容预览:
  • 点击上方 &;程序员小乐&; ,选择“置顶公众号”,第一时间送达! 每日英文...~
  • (2) i >= maxidR 这时候没有任何的已知信息,我们只能从i的左右两边...~
  •        p指的是原始数组中的值~

始发于微信公众号: 程序员小乐

专注于编程、互联网动态。最终将总结的技术、心得、经验(数据结构与算法、源码分析等)分享给大家,这里不只限于技术!还有职场心得、生活感悟、以及面经点击上方 “程序员小乐” ,选择“置顶公众号”,第一时间送达!


每日英文
Most importantly; just keep smiling, because life is a beautiful thing, and there’s so much to smile about.
人生最要紧的就是要保持微笑。生命如此美妙,有太多的事,都值得微笑以对。

乐乐有话说
圆规为什么可以画圆?因为脚在走,心不变;你为什么不能圆梦?因为心不定,脚不动。

面试算法代码知识梳理系列


 一、概要


本文介绍了有关字符串的算法第二部分的Java代码实现,所有代码均可通过 在线编译器 (https://tool.lu/coderunner/)直接运行,算法目录:

  • 查找字符串中的最长重复子串

  • 求长度为N的字符串的最长回文子串

  • 将字符串中的移到前部,并且不改变非的顺序

  • 不开辟用于交换的空间,完成字符串的逆序C++

  • 最短摘要生成

  • 最长公共子序列

 二、代码实现


2.1 查找字符串中的最长重复子串

问题描述

给定一个文本文件作为输入,查找其中最长的重复子字符串。例如,”Ask not what your country can do for you, but what you can do for your country”中最长的重复字符串是“can do for you”,第二长的是”your country”。

解决思路

这里解决问题的时候用到了 后缀数组 的思想,它指的是字符串所有右子集的集合,例如字符串abcde,它的后缀数组就为[“abcde”, “bcde”, “cde”, “de”, “e”]。

解法分为三步:

  • 求得输入字符串p的后缀数组,把它存放在一个List当中,这里注意去掉空格的情况。

  • 对List中的所有元素进行快速排序。快速排序的目的不在于使得整个数组有序,而在于 使得前缀差异最小的两个字符串在数组中位于相邻的位置,对于上面的例子,其排序结果为:

面试算法知识梳理三:字符串算法第二部分后缀数组的快速排序结果

遍历排序后的数组,只需要对数组中的 相邻的两个元素 从头开始比较,计算出这两个字符串相同前缀的长度。遍历之后,取得的最大值就是最长重复子串的长度,而这两个字符串的相同前缀就是最长重复子串。

实现代码

import java.util.ArrayList;
import java.util.List;
import java.lang.String;
class Untitled {
   static void quickSortStr(List<String> c, int start, int end){
       if(start >= end)
           return;
       int pStart = start;
       int pEnd = end;
       int pMid = start;
       String t = null;
       for (int j = pStart+1; j <= pEnd; j++) {
           if ((c.get(pStart)).compareTo(c.get(j)) > 0) {
               pMid++;
               t = c.get(pMid);
               c.set(pMid, c.get(j));
               c.set(j, t);
           }
       }
       t = c.get(pStart);
       c.set(pStart, c.get(pMid));
       c.set(pMid, t);
       quickSortStr(c, pStart, pMid-1);
       quickSortStr(c, pMid+1, pEnd);
   }
   //获得两个字符串从第一个字符开始,相同部分的最大长度。
   static int comLen(String p1, String p2){
       int count = 0;
       int p1Index = 0;
       int p2Index = 0;
       while (p1Index < p1.length()) {
           if (p1.charAt(p1Index++) != p2.charAt(p2Index++))
               return count;
           count++;
       }
       return count;
   }
   static String longComStr(String p, int length){
       List<String> dic = new ArrayList<String>();
       int ml = 0 ;
       for (int i = 0; i < length; i++) {
           if (p.charAt(i) != ' ') {
               //构造所有的后缀数组。
               dic.add(p.substring(i, p.length()));
           }
       }
       String mp = null;
       //对后缀数组进行排序。
       quickSortStr(dic, 0, dic.size()-1);
       //打印排序后的数组用于调试。
       for (int i = 0; i < dic.size(); i++) {
           System.out.println("index=" + i + ",data=" + dic.get(i));
       }
       for (int i = 0; i < dic.size()-1; i++) {
           int tl = comLen(dic.get(i), dic.get(i+1));
           if (tl > ml) {
               ml = tl;
               mp = dic.get(i).substring(0, ml);
           }
       }
       return mp;
   }
   public static void main(String[] args) {
       String source = "Ask not what your country can do for you, but what you can do for your country";
       System.out.println("result = " + longComStr(source, source.length()));
   }
}

运行结果

result = can do for you

2.2 求长度为 N 的字符串的最长回文子串
问题描述

长度为N的字符串,求这个字符串里的最长回文子串,回文字符串 简单来说就是一个字符串正着读和反着读是一样的。

解决思路

这里用到的是Manacher算法,首先需要对原始的字符串进行预处理,即在每个字符之间加上一个标志位,这里用#来表示,这会使得对于任意一个输入,经过处理后的字符串长度为2*len+1,也就是说 处理后的字符串始终为奇数。

在上面我们已经介绍过,回文串中最左或最右位置的字符与其对称轴的距离称为 回文半径,Manacher定义了一个数组RL[i],它表示 第i个字符为对称轴的回文串 的 最右一个字符与字符i的闭区间所包含的字符个数,以google为例,经过处理后的字符串为#g#o#o#g#l#e,那么RL[i]的值为:

面试算法知识梳理三:字符串算法第二部分

而RL[i]-1的值就是原始字符串中,以位置i为对称轴的最长回文串的长度,那么接下来的问题就变成如何计算RL[i]数组。
首先,我们需要两个辅助的变量maxidR和maxid,它表示当前计算的回文字符串中,所能触及到的最右位置,而maxid则表示该回文串的对称轴所在位置,而RL[maxid]为该回文串的距离。

假设我们此时遍历到了第i个字符,那么这时候有两种情况:

(1) i < maxidR

在这种情况下,我们知道p[maxid+1, .., maxid+RL[maxid]-1]和p[maxid-1, .., maxid-RL[maxid]+1]部分是关于p[maxid]对称的,利用这个有效信息,可以避免一些不必要的判断。

现在,我们获得i关于maxid的对称点j,这个点位于maxid的左侧,因此,我们已经计算过以它为中心的回文字符串长度RL[j],对于以p[j]为中心的回文字符串有两种情况:

以j为中心的回文字符的最左边j-(RL[j]-1) 大于等于 maxidR关于maxid的对称点maxid-(maxidR-maxid),在这种情况下,我们可以推断出以i为对称点的RL[i]的值最小为RL[j]。
大于的情况,可以保证以i为对称点的RL[i]至少为(maxidR-i)+1。
当然这上面只是推测出的 最小情况,之后仍然要继续遍历来更新RL[i]的值。

(2) i >= maxidR

这时候没有任何的已知信息,我们只能从i的左右两边慢慢遍历。

实现代码

class Untitled {
   static int maxSynStr(char ip[], int len) {
       int size = 2*len + 1;
       char a[] = new char[size];
       int RL[] = new int[size];
       int i = 0;
       int n;
       while (i < len) {
           a[(i<<1)+1] = ip[i];
           a[(i<<1)+2] = '#';
           i++;
       }
       a[0] = '#';
       //最远字符的中心对称点。
       int maxid = 0;
       //探索到的最远字符。
       int maxidR = 0;
       int ans = 0;
       RL[0] = 1;
       for (i = 1; i < size; i++) {
           //首先推测出i为中心的最小回文半径。
           int offset = 0;
           if (i < maxidR) {
               //j是关于maxid在左边的对称点。
               int j = maxid-(i-maxid);
               //获取之前计算出的以j为中心的回文半径。
               if (j-(RL[j]-1) >= maxid-(maxidR-maxid)) {
                   offset = RL[j]-1;
               } else {
                   offset = maxidR-maxid;
               }
           }
           do {
               offset++;
           } while(i-offset >= 0 && i+offset < size && a[i+offset] == a[i-offset]);
           //最后一次是匹配失败的,因此要减去1。
           offset--;
           //RL[i]的值包括了自己,因此要加1。
           RL[i] = offset+1;
           //更新当前最大的回文半径。
           if (i+offset > maxidR){
               maxidR = i+offset;
               maxid = i;
           }
           if (RL[i] > ans) {
               ans = RL[i];
           }
       }
       return ans-1;
   }
   public static void main(String[] args) {
       char[] source = "google".toCharArray();
       System.out.println("result=" + maxSynStr(source, 6));
   }
}

运行结果:

result=4

2.3 将字符串中的 * 移到前部,并且不改变非 * 的顺序
问题描述

将字符串中的移到前部,并且不改变非的顺序,例如abcde12,处理后为abcde12。

解决思路

我们可以将整个数组分为两个部分:有可能包含字符的部分和一定不包含字符的部分。初始时候,整个数组只有有 有可能包含字符的部分,那么我们就可以 从后往前 遍历,每遇到一个非的字符就把它放到 一定不包含字符的部分,由于需要保持非的顺序,因此需要将它插入到该部分的首部。

实现代码

class Untitled {
   static void moveNullCharPos(char p[], int length) {
       if (length > 1) {
           char t;
           char c;
           int lastCharIndex = length;
           //必须要从后向前扫描。
           for(int j = length-1; j >=0 ;j--) {
               if ((c = p[j]) != '*') {
                   lastCharIndex--;
                   t = p[lastCharIndex]; p[lastCharIndex] = p[j]; p[j] = t;
               }
           }
       }
       System.out.println(p);
   }
   public static void main(String[] args) {
       char[] source = "ab**cd**e*12".toCharArray();
       moveNullCharPos(source, source.length);
   }
}

运行结果:

*abcde12

2.4 不开辟用于交换的空间,完成字符串的逆序(C++)
问题描述

不开辟用于交换的空间,完成字符串的逆序。

解决思路

这里利用的是 两次亦或等于本身 的思想。

实现代码

#include <iostream>
using namespace std;
void reverWithoutTemp(char *p, int length){
   int i = 0;
   int j = length-1;
   while (i < j) {
       p[i] = p[i]^p[j];  
       //实际上是p[i]^p[j]^p[j],这里的p[i]和p[j]指的是原始数组中的值。
       p[j] = p[i]^p[j];  
       //实际上是(p[i]^(p[i]^p[j]^p[j]))^(p[i]^p[j]^p[j]),这里的p[i]和p[j]指的是原始数组中的值。
       p[i] = p[i]^p[j];  
       i++;j--;
   }
   std::cout << p << std::endl;
}
int main() {
   char p[] = "1234566";
   reverWithoutTemp(p, 7);
   return 0;
}

运行结果:

6654321

2.5 最短摘要生成
问题描述

给定一段描述w和一组关键字q,我们从这段描述中找出包含所有关键字的最短字符序列,这个最短字符序列就称为 最短摘要:

  • 最短字符序列必须包含所有的关键字

  • 最短字符序列中关键字的顺序可以是随意的

解决思路

假设我们的输入序列如下所示,其中w表示非关键字的字符串,而q则表示关键字的字符串:

w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1

这里,我们引入额外的三个变量pStart、pEnd和flag数组,flag数组用于统计pStart和pEnd之间关键字的命中情况。

这里说明一下flag数组的作用,flag数组和关键字p数组的长度相同,每命中一个关键字,就将flag数组的对应位置+1,而flagSize只有在每次遇到一个新的关键字时才更新,因此它表示flag数组中 不重复的关键字的个数。

算法的步骤如下:

  • 第一步:我们将pEnd从w[0]开始移动,每发现一个命中的关键字,就更新flag[]数组,直到w[pStart,..,pEnd] 包含了所有的关键字,即w0,w1,w2,w3,q0,w4,w5,q1。

  • 第二步:开始移动pStart,这时候pStart,..,pEnd之间的长度将会逐渐变短,在移动的过程中,同时更新flag[]数组,直到pStart,…,pEnd之间 不再包含所有的关键字,这时候就可以求得 目前为止的最短摘要长度,即q0,w4,w5,q1。

  • 第三步:重复第一步的操作,移动pEnd使得pStart,…,pEnd重新 包含所有的关键字,再执行第二步的操作来 更新最短摘要长度,直到pEnd遍历到w的最后一个元素。

实现代码

class Untitled {
   static int findKey(String[] p1, String p2) {
       int len = p1.length;
       for(int i = 0; i < len; i++) {
           if(p1[i].equals(p2))
               return i;
       }
       return -1;
   }
   //p1为原始数据,p2为所有的关键词。
   static int calMinAbst(String[] p1, String[] p2) {
       int p1Len = p1.length;
       int p2Len = p2.length;
       int r;
       int shortAbs = Integer.MAX_VALUE;
       int tAbs = 0;
       int pBegin = 0;
       int pEnd = 0;
       int absBegin = 0;
       int absEnd = 0;
       int flagSize = 0;
       int flag[] = new int[p2Len];
       //初始化标志位数组。
       for (int i = 0; i < p2Len; i++) {
           flag[i] = 0;
       }
       while (pEnd < p1Len) {
           //只有先找到全部的关键词才退出循环。
           while (flagSize != p2Len && pEnd < p1Len) {
               r = findKey(p2, p1[pEnd++]);
               if (r != -1) {
                   if (flag[r] == 0) {
                       flagSize++;
                   }
                   flag[r]++;
               }
           }
           while (flagSize == p2Len) {
               if ((tAbs = pEnd-pBegin) < shortAbs) {
                   shortAbs = tAbs;
                   absBegin = pBegin;
                   absEnd = pEnd-1;
               }
               r = findKey(p2, p1[pBegin++]);
               if (r != -1) {
                   flag[r]--;
                   if (flag[r] == 0) {
                       flagSize--;
                   }
               }
           }
       }
       for (int i = absBegin; i <= absEnd; i++) {
           System.out.print(p1[i] + ",");
       }
       System.out.println("n最短摘要长度=" + tAbs);
       return shortAbs;
   }
   public static void main(String[] args) {
       String keyword[] = {"微软", "计算机", "亚洲"};
       String str[] = {
           "微软","亚洲","研究院","成立","于","1998","年",",","我们","的","使命",
           "是","使","未来","的","计算机","能够","看","、","听","、","学",",",
           "能","用","自然语言","与","人类","进行","交流","。","在","此","基础","上",
           ",","微软","亚洲","研究院","还","将","促进","计算机","在","亚太","地区",
           "的","普及",",","改善","亚太","用户","的","计算","体验","。","”"
       };
       calMinAbst(str, keyword);
   }
}

运行结果

微软,亚洲,研究院,还,将,促进,计算机,
最短摘要长度=7

2.6 最长公共子序列
问题描述

经典的LCS问题,这里主要解释一下最长公共子序列的含义。最长公共子串和最长公共子序列的区别:子串是 串的一个连续的部分,子序列则是 不改变序列的顺序,而从序列中去掉任意的元素 而获得的新序列。

解决思路

经典的LCS问题,原理可以参考这篇被广泛转载的文章 程序员编程艺术第十一章:最长公共子序列问题,这里给出简要介绍一下基本的思想。

https://blog.csdn.net/v_july_v/article/details/6695482

LCS基于下面这个定理:

面试算法知识梳理三:字符串算法第二部分

LCS 算法定理

最终目的是构建类似于下面的一个矩阵:

面试算法知识梳理三:字符串算法第二部分

LCS 矩阵

  • 对于矩阵,定义c[i][j]:它表示字符串序列A的前i个字符组成的序列A和字符串序列B的前j个字符组成的序列B之间的最长公共子序列的长度,其中i<=A.len,并且j<=B.len。

  • 如果A[i]=B[j],那么A与B之间的最长公共子序列的最后一项一定是这个元素,也就是c[i][j] = c[i-1][j-1]+1。

  • 如果A[i]!=B[j],则c[i][j]= max(c[i-1][j], c[i][j-1])。

  • 初始值为:c[0][j]=c[i][0]=0。

代码实现

class Untitled {
   static void LCS(char a[], int aLen, char b[], int bLen){
       int c[][] = new int[bLen+1][aLen+1];
       for (int i = 1; i < bLen+1; i++) {
           for (int j = 1; j < aLen+1; j++) {
               if (a[j-1] == b[i-1]) {
                   c[i][j] = c[i-1][j-1] + 1;
               } else {
                   c[i][j] = (c[i-1][j]>c[i][j-1]) ? c[i-1][j]:c[i][j-1];
               }
           }
       }
       int csl = c[bLen][aLen];
       char p[] = new char[csl+1];
       int i = bLen, j = aLen;
       while (i > 0 && j > 0 && c[i][j] > 0) {
           if (c[i][j] == c[i-1][j]) {
               i--;
           } else if(c[i][j] == c[i][j-1]) {
               j--;
           } else if(c[i][j] > c[i-1][j-1]) {
               p[c[i][j]] = a[j-1];
               i--;j--;
           }
       }
       for (i = 1; i <= csl; i++) {
           System.out.print(p[i]);
       }
   }
   public static void main(String[] args) {
       char p1[] = "aadaae".toCharArray();
       char p2[] = "adaaf".toCharArray();
       LCS(p1, p1.length, p2, p2.length);
   }
}

运行结果

adaa

如何您想进技术群交流,关注公众号在后台回复 “加群”,或者 “学习” 即可

来自:泽毛

链接:https://www.jianshu.com/p/9839d0c7a521

著作权归作者所有,欢迎投稿。

面试算法知识梳理三:字符串算法第二部分


推荐阅读






看完本文有收获?请转发分享给更多人
关注「程序员小乐」,提升技能

以上就是:面试算法知识梳理三:字符串算法第二部分 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论