九十三.字符串匹配 KMP、suffix array 、RabinKarp (字符串算法问题（二）)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了九十三.字符串匹配 KMP、suffix array 、RabinKarp (字符串算法问题（二）)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4775字，纯文字阅读大概需要7分钟。
内容图文
暴力解法：
import java.util.Scanner;
public class LianXi {
public static int index(String s, String p){
int i = 0;
int sc = i;
int j = 0;
while(sc < s.length()){
if(s.charAt(sc) == p.charAt(j)){
sc++;
j++;
if(j == p.length())
return i;
}
else{
i++;
sc = i;
j = 0;
}
}
return -1;
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
String s = in.next();
String p = in.next();
int res = index(s,p);
System.out.println(res);
}
}
KMP：
import java.util.Scanner;
public class LianXi {
public static int index(String s, String p){
if(s.length() == 0 || p.length() == 0)
return -1;
if(p.length() > s.length())
return -1;
int[] next = next(p);
int i = 0; //s位置
int j = 0; //p位置
int slen = s.length();
int plen = p.length();
while(i < slen){
//①如果 j==-1,或者当前字符串匹配成功，(即s[i] == p[j]),都令i++,j++
//j=-1,即next[0]=-1,说明p的第一位和i在这个位置无法匹配，这时i,j都增加1，i移位，j从0开始
if(j==-1 || s.charAt(i) == p.charAt(j)){
i++;
j++;
}else{
//②如果 j!= -1, 且当前字符匹失败(即s[i]！=p[j]),则令i不变,j=next[j]
//next[j]即为j所对应的next值
j = next[j];
}
if(j == plen)
return (i - j);
}
return -1;
}
public static int[] next(String ps){
int plength = ps.length();
int[] next = new int[plength];
char[] p = ps.toCharArray();
next[0] = -1;
if(ps.length() == 1)
return next;
next[1] = 0;
int j = 1;
int k = next[j]; // 看看位置j的最长匹配前缀在哪里
while(j < plength - 1){
//现在要推出next[j+1],检查j和k位置上的关系即可
if(k < 0 || p[j] == p[k]){
next[++j] = ++k;
}else{
k = next[k];
}
}
return next;
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
String s = in.next();
String p = in.next();
int res = index(s,p);
System.out.println(res);
}
}
后缀数组：
import java.util.Arrays;
public class Match03_SuffixArray {
public static int[] getHeight(String src, Suff[] sa) {
// Suff[] sa =getSa2(src);
int strLength = src.length();
int[] rk = new int[strLength];
//将rank表示为不重复的排名即0~n-1
for (int i = 0; i < strLength; i++) {
rk[sa[i].index] = i;
}
int[] height = new int[strLength];
int k = 0;
for (int i = 0; i < strLength; i++) {
int rk_i = rk[i];//i后缀的排名
if (rk_i == 0) {
height[0] = 0;
continue;
}
int rk_i_1 = rk_i - 1;
int j = sa[rk_i_1].index;//j是i串字典序靠前的串的下标
if (k > 0) k--;
for (; j + k < strLength && i + k < strLength; k++) {
if (src.charAt(j + k) != src.charAt(i + k))
break;
}
height[rk_i] = k;
}
return height;
}
public static Suff[] getSa2(String src) {
int n = src.length();
Suff[] sa = new Suff[n];
for (int i = 0; i < n; i++) {
sa[i] = new Suff(src.charAt(i), i, src);//存单个字符,接下来排序
}
Arrays.sort(sa);
/**rk是下标到排名的映射*/
int[] rk = new int[n];//suffix array
rk[sa[0].index] = 1;
for (int i = 1; i < n; i++) {
rk[sa[i].index] = rk[sa[i - 1].index];
if (sa[i].c != sa[i - 1].c) rk[sa[i].index]++;
}
//倍增法
for (int k = 2; rk[sa[n - 1].index] < n; k *= 2) {
final int kk = k;
Arrays.sort(sa, (o1, o2) -> {
//不是基于字符串比较,而是利用之前的rank
int i = o1.index;
int j = o2.index;
if (rk[i] == rk[j]) {//如果第一关键字相同
if (i + kk / 2 >= n || j + kk / 2 >= n)
return -(i - j);//如果某个后缀不具有第二关键字,那肯定较小,索引靠后的更小
return rk[i + kk / 2] - rk[j + kk / 2];
} else {
return rk[i] - rk[j];
}
});
/*---排序 end---*/
// 更新rank
rk[sa[0].index] = 1;
for (int i = 1; i < n; i++) {
int i1 = sa[i].index;
int i2 = sa[i - 1].index;
rk[i1] = rk[i2];
try {
if (!src.substring(i1, i1 + kk).equals(src.substring(i2, i2 + kk)))
rk[i1]++;
} catch (Exception e) {
rk[i1]++;
}
}
}
return sa;
}
public static class Suff implements Comparable<Suff> {
public char c;//后缀内容
private String src;
public int index;//后缀的起始下标
public Suff(char c, int index, String src) {
this.c = c;
this.index = index;
this.src = src;
}
@Override
public int compareTo(Suff o2) {
return this.c - o2.c;
}
@Override
public String toString() {
return "Suff{" +
"char='" + src.substring(index) + '\'' +
", index=" + index +
'}';
}
}
}
RabinKarp
public class Match01_RabinKarp {
public static void main(String[] args) {
String s = "ABABABA";
String p = "ABA";
match(p, s);
}
private static void match(String p, String s) {
long hash_p = hash(p);//p的hash值
long[] hashOfS = hash(s, p.length());
match(hash_p, hashOfS);
}
private static void match(long hash_p, long[] hash_s) {
for (int i = 0; i < hash_s.length; i++) {
if (hash_s[i] == hash_p) {
System.out.println("match:" + i);
}
}
}
final static long seed = 31;
static long[] hash(final String s, final int n) {
long[] res = new long[s.length() - n + 1];
//前m个字符的hash
res[0] = hash(s.substring(0, n));
for (int i = n; i < s.length(); i++) {
char newChar = s.charAt(i);
char ochar = s.charAt(i - n);
//前n个字符的hash*seed-前n字符的第一字符*seed的n次方
long v = (res[i - n] * seed + newChar - Case11_NExponent.ex2(seed, n) * ochar) % Long.MAX_VALUE;
res[i - n + 1] = v;
}
return res;
}
static long hash(String str) {
long h = 0;
for (int i = 0; i != str.length(); ++i) {
h = seed * h + str.charAt(i);
}
return h % Long.MAX_VALUE;
}
}
内容总结
以上是互联网集市为您收集整理的九十三.字符串匹配 KMP、suffix array 、RabinKarp (字符串算法问题（二）)全部内容，希望文章能够帮你解决九十三.字符串匹配 KMP、suffix array 、RabinKarp (字符串算法问题（二）)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】