2025年GST算法的实现（java）

科技前沿 • 2025-04-10 21:09 • 阅读 21

大家好，我是讯享网，很高兴认识大家。

GST算法（贪婪式字符串匹配算法）简介：

是一种基于token的字符串相似度算法。基本思想为：如果两个字符串完全相同，则返回一个最大值，该值与较短字符串的长度相同。如果两个串完全不相同，则返回最小值0.通常经较长串称为文本串，较短串称为模式串。在使用GST算法时还会定义一个最小匹配长度，然后得到所有大于或者等于这个长度的不重叠的匹配字段，将这些字段长度和作为结果。

算法流程说明：

1.首先假设两段字符串为A和B，最小匹配长度为minlen，定义一个match集合和list集合，match存放每次循环中匹配的字符串，list为最终的到的匹配集合。

讯享网

以下是具体代码

package Lexer; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class GST { static List<String> list = new ArrayList<String>();//存放最终得到的匹配 static List<String> match = new ArrayList<String>();//存放每次得到的最大匹配 static int start_point1[];//记录每次得到的匹配在字符串A和B中的起始位置，用于标记 static int start_point2[]; public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.println("请输入第一段字符串"); String s1 = in.next(); System.out.println("请输入第二段字符串"); String s2 = in.next(); start_point1 = new int[s1.length()]; start_point2 = new int[s2.length()]; gst(s1,s2,2); System.out.println("有"+list.size()+"个匹配"); for(String s:list){ System.out.println(s); } } public static void gst(String s1,String s2,int minlen){ list.clear(); int start_point_sum = 0; int len1 = s1.length(); int len2 = s2.length(); int mark1[] = new int[len1];//记录字符串A和B中被标记的位 int mark2[] = new int[len2]; int now_minlen = minlen+1; while(now_minlen > minlen){ now_minlen = minlen; match.clear(); int start1 = 0; int start2 = 0; for(int i = 0;i<len1;i++){ if(mark1[i]==0){ for(int j = 0;j<len2;j++){ if(mark2[j]==0){ int a = 0; String str = ""; char c1 = 0; char c2 = 0; while(c1==c2&&(i+a)<len1&&(j+a)<len2){//得到从当前位置开始能得到的匹配 c1 = s1.charAt(i+a); c2 = s2.charAt(j+a); str+=c1; a++; } if(a==now_minlen){ match.add(str); start1 = i; start2 = j; start_point1[start_point_sum] = i; start_point2[start_point_sum] = j; start_point_sum++; }else if(a > now_minlen){ start_point_sum = 0; now_minlen = a; match.clear(); match.add(str); start_point1[start_point_sum] = i; start_point2[start_point_sum] = j; start_point_sum++; } } } } } //System.out.println(match.size()+""); if(match.size()>0){ for(String s:match){ list.add(s); } for(int i = 0;i<start_point_sum;i++){//将相应段标记 for(int j = 0;j<now_minlen;j++){ mark1[j+start_point1[i]] = 1; mark2[j+start_point2[i]] = 1; } } } } } }

讯享网

运行实例

讯享网请输入第一段字符串 abcdef 请输入第二段字符串 defabc 有2个匹配 abc def

2025年GST算法的实现（java）

相关推荐