t**g
发帖数: 1164 | 1 就是给一个很长的字符串str
还有一个字符集比如{a,b,c}
找出str里包含{a,b,c}的最短子串
要求O(n)?
thanks |
Z*****Z
发帖数: 723 | 2 这样做可不可以？
假设ASCII字符，范围0-255。
假设做给字符集合c1，c2，...ck
用一个大小为256的int数组T记录当前所查找的子字符串包含给定字符的情况。
T[*] = -1;
T[ci] = 0;
用一个整数变量d记录未找到字符个数
d = k;
两个指针p，q
第1步，找到第一个符合条件的子字符串
第1.1步，找到第一个符合条件的子字符。用p从头扫描给定字串，如果不在给定字符集
合中，重复1.1。否则到1.2
第1.2步，假设p指向cj，那么T[cj]++，d--，q指向p+1
第1.3步，用q向后扫描寻找剩下的字符，每次找到一个cl，则：
if(T[cl] == 0){
d--;
}
T[cl]++
第1.4步，重复1.3直到到达所给字符串末尾（不存在那样的子串），或者d变成0（找到
第1个符合条件的子串）
记录当前子串长度L，
第2步，扫描剩下的字串，寻找更优解
第2.1步，用q继续向后扫描，每次发现cj，则T[cj]++，到2.2
第2.2步，
while(T[*p] != 1){
if(T[*p] > 1){
【在 t**g 的大作中提到】
: 就是给一个很长的字符串str
: 还有一个字符集比如{a,b,c}
: 找出str里包含{a,b,c}的最短子串
: 要求O(n)?
: thanks
|
l******c
发帖数: 2555 | 3 copy & paste from web site, anybody can explain?
Algorithm:
step 1:
add next character to string
Optimize string
if we have a substring
Record substring if its the best so far
step 2:
remove leftmost character from string
If we still have a substring
Optimize substring
Record substring if its the best so far
goto step 2
goto step 1 |
r****o
发帖数: 1950 | 4 where is the URL?
【在 l******c 的大作中提到】
: copy & paste from web site, anybody can explain?
: Algorithm:
: step 1:
: add next character to string
: Optimize string
:
: if we have a substring
: Record substring if its the best so far
:
: step 2:
|
Z*****Z
发帖数: 723 | 5 这个算法有点小问题。
这是改进之后的算法实现。
请拍
public class ShortestSubString {
/**
*
* ASCII characters are assumed here
*
* @param str - input string
* @param charSet - a set of characters
* @return
*/
static public String findShortestSubString(String str, Set
> charS
et){
if(charSet == null || charSet.size() == 0 || str == null){
return null;
}
【在 Z*****Z 的大作中提到】
: 这样做可不可以？
: 假设ASCII字符，范围0-255。
: 假设做给字符集合c1，c2，...ck
: 用一个大小为256的int数组T记录当前所查找的子字符串包含给定字符的情况。
: T[*] = -1;
: T[ci] = 0;
: 用一个整数变量d记录未找到字符个数
: d = k;
: 两个指针p，q
: 第1步，找到第一个符合条件的子字符串
|
f*********5
发帖数: 576 | 6 lo=0;hi=0; min=sizeof(str);
while(*str!='\0')
{
if (*str) not in target chars
{ str++;
if !(***)lo++;
hi++;
continue;
}
flag for *str ++;
if( all the flag for target chars >=1)
{ if (hi-lo
set lo to next location that target chars happened in the
str;
flag for *str --;
}
hi++;
}
【在 t**g 的大作中提到】
: 就是给一个很长的字符串str
: 还有一个字符集比如{a,b,c}
: 找出str里包含{a,b,c}的最短子串
: 要求O(n)?
: thanks
|
Z*****Z
发帖数: 723 | 7
~~~~~~什么意思？
【在 f*********5 的大作中提到】
: lo=0;hi=0; min=sizeof(str);
: while(*str!='\0')
: {
: if (*str) not in target chars
: { str++;
: if !(***)lo++;
: hi++;
: continue;
: }
: flag for *str ++;
|
f*********5
发帖数: 576 | 8 不好意思，懒得写了
就是字符串一开始的时候，遇见非target字符，lo/hi都递增
当你已经开始找到至少一个target字符时，就应该固定这个lo了
就不要变了。
当你找到一个区间包含所有字符的时候，就又相当于重新开始
就又可以lo++，hi++了
【在 Z*****Z 的大作中提到】
:
: ~~~~~~什么意思？
|
Z*****Z
发帖数: 723 | 9
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
这一步有可能会漏掉最优解
例如，输入aabcd，字符集合为abc
当扫描到c的时候，不应该同时增加lo和hi，应该只试图增加lo
【在 f*********5 的大作中提到】
: 不好意思，懒得写了
: 就是字符串一开始的时候，遇见非target字符，lo/hi都递增
: 当你已经开始找到至少一个target字符时，就应该固定这个lo了
: 就不要变了。
: 当你找到一个区间包含所有字符的时候，就又相当于重新开始
: 就又可以lo++，hi++了
|
w******1
发帖数: 520 | 10 用树来做。
Generalized Suffix Tree |
Z*****Z
发帖数: 723 | 11 能具体点么？
【在 w******1 的大作中提到】
: 用树来做。
: Generalized Suffix Tree
|
y****n
发帖数: 579 | 12 给个单词的集合，找出同一页面上集合中单词出现的最小区间也能这么做吗？
【在 Z*****Z 的大作中提到】
: 这个算法有点小问题。
: 这是改进之后的算法实现。
: 请拍
: public class ShortestSubString {
:
: /**
: *
: * ASCII characters are assumed here
: *
: * @param str - input string
|
P********l
发帖数: 452 | |
