By

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码

题目

最短摘要生成
给定一个字符串，以及一系列查询词，在这个字符串中找到一个子串，该子串包含全部的查询词，求这个最短子串

解析

两个指针，begin和end
首先使用end往右边移动一直移动到全部包含查询字符集q的位置
然后将begin也向右边移动，直达再移动一次begin-end区间里面的数据将不再包含q
此时记录begin和end以及其最小的间距
然后begin右移一位，end继续右边移动直至全部包含，周而复始

代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
private int minBegin=-1;
private int minEnd=-1;

private int curBegin=-1;
private int curEnd=-1;

/**
 * 最短摘要生成的匹配
 * 两个指针，begin和end
 * 首先使用end往右边移动一直移动到全部包含查询字符集q的位置
 * 然后将begin也向右边移动，直达再移动一次begin-end区间里面的数据将不再包含q
 * 此时记录begin和end以及其最小的间距
 * 然后begin右移一位，end继续右边移动直至全部包含，周而复始
 * 代码中查询是否全部包含使用了位操作，这样更加快^_^
 * @param data
 * @param q
 * @return
 */
public String match(String data,char[] q)
{
	int matchs=0;//存储匹配的情况
	int matchIndex=-1;
	curBegin=-1;
	curEnd=0;
	while(curEnd<data.length())
	{
		if((matchIndex=indexOf(q,data.charAt(curEnd)))>=0)
		{
			if(curBegin==-1)
				curBegin=curEnd;//初始化第一次开始匹配项
			
			matchs|=1<<matchIndex;//存储到匹配库
			if(matchs==(1<<q.length)-1)//全部匹配
			{
				
				if(minBegin==-1 || (minEnd-minBegin)>(curEnd-curBegin))
				{
					//更新最短摘要
					minBegin=curBegin;
					minEnd=curEnd;
				}
				
				matchs^=indexOf(q,data.charAt(curBegin));//去掉首位匹配
				while(data.charAt(++curBegin)<0);//将首位匹配移至第二位
			}
		}
		
		curEnd++;
	}
	
	if(minBegin!=-1)
	{
		char[] rc=new char[minEnd-minBegin+1];
		int i=0;
		while(minBegin<=minEnd)
		{
			rc[i++]=data.charAt(minBegin++);//取值
		}
		
		minBegin=-1;
		return String.valueOf(rc);
	}else{
		return "";
	}
	
}


/**
 * 查找当前字符在数组中的位置
 * @param q
 * @param d
 * @return 没有找到则返回-1
 */
private int indexOf(char[] q,char d)
{
	int index=-1;
	for(int i=0;i<q.length;i++)
	{
		if(q[i]==d)
		{
			index=i;
			break;
		}
	}
	
	return index;
}

测试的代码为

1
2
3
4
5
6
7
public static void main(String[] args) {
	char[] q={'a','b','s','d'};
	String data="hello are you bottom of ado the is bot doke astringadb";
	//String data="abd";
	
	System.out.println(new ShortAbstract().match(data, q));
}

输出的结果为

are you bottom of ado the is

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码