JSRUN 用代码说话
傻也不懂
shayebudong
JSRUN的第33592位用户
加入于 2020-09-14
上次活跃 2020-09-14



public class HelloWorld {
    public static void main(String[] args) {
        // char[] a = { '记','录','模','式','串','中','每','个','字','符','最','后','出','现','的','位','置' };      
        // char[] b = { '每','个','字'};

        char[] a = { 'I', 'L', 'o', 'v', 'e', 'C', 'o', 'd', 'e' };      
        char[] b = { 'd', 'e'};


        System.out.println("asccii  "+ (int)'式');
        System.out.println("char [] 长度" +a.length);
        int index = BM(a,a.length,b,b.length);
        System.out.println("查找到的位置在第 "+ index+" 个");

    }

    private static final int SIZE = 256; // 全局变量或成员变量

    // a,b表示主串和模式串;n,m表示主串和模式串的长度。
    public static int BM(char[] a,int n,char[] b,int m) {
        int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
        generateBC(b, m, bc); // 构建坏字符哈希表
        int[] suffix = new int[m];
        boolean[] prefix = new boolean[m];
        generateGS(b, m, suffix, prefix);
        int i = 0; // j表示主串与模式串匹配的第一个字符
        while (i <= n - m) {
            int j;
            for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
            if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是j
            }
            if (j < 0) {
            return i; // 匹配成功,返回主串与模式串第一个匹配的字符的位置
            }
            int x = j - bc[(int)a[i+j]];
            int y = 0;
            if (j < m-1) { // 如果有好后缀的话
            y = moveByGS(j, m, suffix, prefix);
            }
            i = i + Math.max(x, y);
        }
        return -1;
    }

    //散列表,数组的下标对应字符的ASCII码值,数组中存储这个字符在模式串中出现的位置
    //注:如果模式串中出现相同的字符那就记录后面的
    /*                   模式串  a  b  d  a
    ASSCII表                     0  1  2  3 (模式串里出现了两个“a”,只会记录一个位置,后面出现的刷新前面的位置)
       a 97        bc: -1 -1 ... 3  1  -1   2 .... -1
       b 98            0  1 ... 97 98 99 100 .... 255
       c 99
       d 100
       .....*/

    //这里的hash算法太简单了,只适合用来匹配字母,如果需要匹配中文那就需要改进hash算法
    public static void generateBC(char[] b, int m, int[] bc) {
        for (int i = 0; i < SIZE; ++i) {
            bc[i] = -1; // 初始化bc
        }
        for (int i = 0; i < m; ++i) { // i递增,巧妙的将出现相同的字符时,后面的将前面的数值覆盖
            int ascii = (int)b[i]; // 计算b[i]的ASCII值
            bc[ascii] = i;
        }
    }

    /*suffix数组说明:表示模式串中后缀子串的长度,下标对应的数组值存储的是,在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值。
        * * * * * * c a b * * * * *
                    ------(这是{u})
           模式串    c a b c a b
                    ------(这是{u*})
                    ↓ ↓ ↓
          起始下标值 0 1 2

        后缀子串  长度  suffix
              b    1   suffix[1] = 2
            a b    2   suffix[2] = 1
          c a b    3   suffix[3] = 0
        b c a b    4   suffix[4] = -1 (找不到就等于-1)
      a b c a b    5   suffix[5] = -1
    c a b c a b    6   suffix[6] = -1
    */

    // b表示模式串,m表示长度,suffix,prefix数组事先申请好了
    public static void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
        for (int i = 0; i < m; ++i) { // 初始化
            suffix[i] = -1;
            prefix[i] = false;
        }
        for (int i = 0; i < m - 1; ++i) { // b[0, i]
            int j = i;
            int k = 0; // 公共后缀子串长度
            while (j >= 0 && b[j] == b[m-1-k]) { // 与b[0, m-1]求公共后缀子串
            --j;
            ++k;
            suffix[k] = j+1; //j+1表示公共后缀子串在b[0, i]中的起始下标
            }
            if (j == -1) prefix[k] = true; //如果公共后缀子串也是模式串的前缀子串
        }
    }

    // j表示坏字符对应的模式串中的字符下标; m表示模式串长度
    public static int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
        int k = m - 1 - j; // 好后缀长度
        if (suffix[k] != -1) return j - suffix[k] +1;
            for (int r = j+2; r <= m-1; ++r) {
                if (prefix[m-r] == true) {
                return r;
                }
            }
            return m;
    }
}
shayebudong (傻也不懂 )- 2020-09-16 1 人
BM算法java版本
#include <cstring>
#include <iostream>

#define XSIZE 4
#define ASIZE 256
#define MAX(x, y) (x) > (y) ? (x) : (y)

using namespace std;

/*
 *bmBc[k]表示坏字符k在模式串中出现的位置距离模式串末尾的最大长度。
 *假设所有字符没有出现在模式串中,默认长度为模式串长度m
 *注意:!!!如果模式串中有重复出现的字符,坏字符表的值是最右边出现位置的值,也就是bmBc[k]最小的值。如果匹配时,坏字符是这个字符,如果i正好是这个字符两次出现的中间位置,这是如果用肉眼看坏字符移动应该是移动模式串让左边的字符匹配到i处的坏字符,但bmBc[k]是右边的k距离末尾的距离。这是不会出错是因为b[k]-(m-1-i)的值一定是一个负值。而i匹配到了模式串中间的位置,这时一定有好后缀,好后缀确定的移动距离一定不是负值,所以这是移动的距离是由好后缀确定的,所以bmBc[k]才可以保存最右边的字符距离末尾的值。
 *
 * */
void preBmBc(const char *x, int m, int bmBc[]) {
	int i;
	for (i = 0; i < ASIZE; ++i) 
	  bmBc[i] = m;
	for (i = 0; i< m - 1; ++i){
	  bmBc[x[i]] = m - i -1;
	}
}

/*
 *suffix数组表示以i为边界,与模式串后缀匹配的最大长度,
 *用公式描述:满足P[i-s, i] == P[m-s, m]
 *如果i不等于m,suffixs[i] 肯定是0,第一个字母都不等。
 * */
void suffixs(const char *x, int m, int *suff) {
	int i, q;	
	suff[m-1] = m; //模式串末尾的前缀是整个模式串
	for (i = m -2; i >= 0; --i) {
		q = i;  //需要两个索引分别表示前缀和后缀的比较的位置
		//这里之所以 +q是用了q在逐渐减小1, 用另外的变量减一也可以。
		while (q >= 0 && x[q] == x[m - 1 - i + q]) 
		  --q;
		suff[i] = i - q;
	}
	
}
/*
 *bmGs[i] 表示遇到好后缀时,模式串应该移动的距离,i表示好后缀前面一个字符的位置
 *bmGs数组分三种情况:
 *1. 模式串有子串匹配上好后缀
 *2. 模式串没有子串匹配上好后缀,但找到一个最大前缀
 *3. 模式串中没有匹配上好后缀,同时也没有最大前缀和好后缀匹配
 * */
void preBmGs(const char *x, int m, int bmGs[]) {
	int i, j, suff[XSIZE];
	suffixs(x, m, suff);
	for (i = 0; i < m; ++i) //没有匹配上子串没有好后缀,移动m
	  bmGs[i] = m;
	j = 0;
	for (i = m - 1; i >= 0; --i) 
		/*
		 *前缀匹配
		 *如果一个字符的最长后缀匹配列长是i+1,
		 *说明匹配到了首字母位置,是好后缀的匹配前缀。
		 *如果i = m - 1,前缀匹配到了后缀,说明完全匹配,搜索结束
		 * */
		if (suff[i] == i + 1) 
		  for(; j < m -1 - i; ++j) //前缀长度i+1,后缀的长度肯定大于 i + 1
			/*
			 * 注意:!!!这里好后缀移动长度从后往前写是因为没有完全匹配最长好后缀的情况下,取匹配好后缀的的最长前缀,这样字符串往后移动最小,这时bmGs[0:i]的移动长度都应该是匹配到最长前缀时移动的长度,前边的bmGS[0:i-1]虽然也可能是匹配到了好后缀(后缀是重复字节的情况),但是他移动的长度过大,错过了几个完全匹配的字符。可能错过匹配。所以,bmGs在匹配到了最长前缀后,只可以更改一次,否则会错过匹配。
			 * */
			if (bmGs[j] == m)
				bmGs[j] = m - 1 - i; 
	for (i = 0; i <= m - 2; ++i) 
	  bmGs[m - 1 - suff[i]] = m - 1 -i;
		/*
		 * 注意:这里当一个字符的suff[i]是0是,计算的是好后缀个数为0时匹配的前缀移动的长度。就是当最末尾一个字符都不等。这时查找的就是suff[i]等于0,即本身和m-1都不等的字符移动到m-1的长度(如果字符和m-1相等,suff[i] >=1)。这时要匹配最右侧一个和m-1不同的值。bmGs[m-1]表示就是m-1没有匹配时的好后缀,这是找最右侧和m-1不同的值就可以了,就是suff[i]==0的字符。i从小到大,bmGs[m-1]最终回去最小的和自己不同的字符位置。
		 * */
}		

void BM(const char *x, int m, const char *y, int n) {
	int i, j, bmGs[XSIZE], bmBc[ASIZE];

	preBmGs(x, m, bmGs);
	preBmBc(x, m, bmBc);

	j = 0;
	while (j <= n - m) {
		for (i = m -1; i >= 0 && x[i] == y[i + j]; --i);
		if (i < 0) {

		  std::cout << "successful" << std::endl;
		  std::cout << j << std::endl;
		  j += bmGs[0];
		  //这里用了如果p[0]不等时的最大好后缀移动长度。加一也可以。
		}
		else {
		  int a = bmGs[i];
		  int b = bmBc[y[i+j]] - m + 1 + i;
		  int c = bmBc[y[i+j]];
		  j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
		}

	}
}

int main()
{
	const char *x = "abab";
	const char *y = "ababab";
	BM(x, strlen(x), y, strlen(y));
}

shayebudong (傻也不懂 )- 2020-09-16 0 人
BM算法C++版
-- 获取字符串的长度(任何单个字符长度都为1)
function getStringLength(inputstr)
    if not inputstr or type(inputstr) ~= "string" or #inputstr <= 0 then
        return nil
    end
    local length = 0  -- 字符的个数
    local i = 1
    while true do
        local curByte = string.byte(inputstr, i)
        local byteCount = 1
        if curByte > 239 then
            byteCount = 4  -- 4字节字符
        elseif curByte > 223 then
            byteCount = 3  -- 汉字
        elseif curByte > 128 then
            byteCount = 2  -- 双字节字符
        else
            byteCount = 1  -- 单字节字符
        end
        -- local char = string.sub(inputstr, i, i + byteCount - 1)
        -- print(char)  -- 打印单个字符
        i = i + byteCount
        length = length + 1
        if i > #inputstr then
            break
        end
    end
    return length
end
--字符串转换为字符数组
--注入string table里面
function toCharArray(str)
    str = str or ""
    local array = {}
    local len = string.len(str)
    local index = 0
    while str do
        local fontUTF = string.byte(str,1)

        if fontUTF == nil then
            break
        end

        local byteCount = 0
        if fontUTF > 0 and fontUTF <= 127 then
            byteCount = 1
           elseif fontUTF >= 192 and fontUTF < 223 then
            byteCount = 2
           elseif fontUTF >= 224 and fontUTF < 239 then
            byteCount = 3
           elseif fontUTF >= 240 and fontUTF <= 247 then
            byteCount = 4
        end
        local tmp = string.sub(str,1,byteCount)
        -- 这里为了方便下面的算法,数组下标统一从0开始计算
        array[index] = tmp
        index = index + 1
        str = string.sub(str,byteCount + 1,len)
    end
    return array
end

local function RK(mainStr,patternStr)
	local m = getStringLength(mainStr)
	local n = getStringLength(patternStr)
	local hash = {}
	local mTable = {}
	local a1 = toCharArray(mainStr)
	local b1 = toCharArray(patternStr)
	local s = 1;
	for i=0,n do -- 将字符串转换成n进制的数字进行存储,方便后面直接取出
		mTable[i] = s
		s = s*n
	end
	for i=0,m-n do
		s = 0
		for j=0,n-1 do
            --  - string.byte("a") 这个好像是多余的
            -- local byte = string.byte(a1[i+j]) - string.byte("a")
            local byte = string.byte(a1[i+j])
			s = s + byte*mTable[n-j]
		end
		hash[i]=s
	end

	s=0
	for j=0,n-1 do
        -- local byte = string.byte(b1[j]) - string.byte("a")
        local byte = string.byte(b1[j])
		s= s + byte*mTable[n-j];
	end
	for j=0,m-n do
		if hash[j]==s then
			return j+1
		end
	end
	return -1
end

local mainStr = "在我这里面查找需要查找的串"
local patternStr = "需要查找的串"
print("查找到的位置在第 "..RK(mainStr,patternStr).." 个(下标从1开始计算)");
shayebudong (傻也不懂 )- 2020-09-14 0 人
RK算法Lua版
public class HelloWorld {
    public static void main(String []args) {
	   String Str = new String("在我这里面需要查找查找的串需要查找的串");
	   String Str2 = new String("需要查找的串");
	   System.out.println("查找到的位置在第 "+rK(Str,Str2)+" 个");
    }

    // 原始模板
    public static int rK(String a,String b) {
		int m=a.length(),n=b.length(),s,j;
        
		int[] hash=new int[m-n+1];
		int[] table=new int[26];
		char[] a1=a.toCharArray();
		char[] b1=b.toCharArray();
		s=1;
		//将26的次方存储在一个表里,取的时候直接用,虽然溢出,但没啥问题
		for(j=0;j<26;j++) {
			table[j]=s;
			s*=26;
		}
		for(int i=0;i<=m-n;i++) {
			s=0;
			for(j=0;j<n;j++) {
                int in = n-1-j;
                // -- -'a' 这个好像是多余的
				// s+=(a1[i+j]-'a')*table[n-1-j]; 
                s+=(a1[i+j])*table[n-1-j]; 
			}
			hash[i]=s;
		}
		s=0;
		for(j=0;j<n;j++) {
            // -'a' 这个好像是多余的
			// s+=(b1[j]-'a')*table[n-1-j];
            s+=(b1[j])*table[n-1-j];
		}
		for(j=0;j<m-n+1;j++) {
			if(hash[j]==s) {
				return j;
			}
		}
		return -1;
	}
}
shayebudong (傻也不懂 )- 2020-09-14 0 人
RK算法的java版本
没有了
1/1
没有了