j**y
发帖数: 462 | 1 不能用java的function
aababccbc remove abc 最后应该""
有啥思路？多谢 |
k*****7
发帖数: 72 | 2 用栈吧，从左到右逐符入栈，遇到c就查栈顶两个是不是ba，是就都pop了，然后继续把
下一个入栈 |
b*****n
发帖数: 482 | 3 How to check the top 2 objects? It seem we can only look at the top
object.
Another question is we have to check N-1 chars from the top of the
stack, where N is the length of the str2. If there are multiple
characters in str2 that are the same as its last char (e.g. accccbc),
then even if str1 is the same as string 2, we have to do extra check 4
times whenever we meet a 'c' in str1.
My idea is to have a companion array recording the maximum matched index
of the char sequence in str1. If there is a total match of str2, remove
it, continue with the next character. Since we recorded the max matched
index of previous char sequence in str1, we can continue the matching
and so on so forth. If there is a mismatch of current character, reset
the array because there won't be any matching of all the previous char
sequence with this mismatched char.
Below is the code. For convenience, used a stack to hold the char seq,
and the output is in reverse order. But the main idea is presented.
#include
#include
#include
using namespace std;
int main()
{
string str1, str2;
cout << "Enter string 1:";
getline(cin, str1);
cout << "Enter string 2:";
getline(cin, str2);
int len1=str1.length();
int len2=str2.length();
// str1 is empty.
if(len1==0) return 0;
//str2 is empty or str1 is shorter than str2.
if((len2==0)||(len1
int *pMatchArray=new int[len1/len2];
for (int i = 0; i<(len1/len2); i++)
*(pMatchArray+i) = -1;
int last = 0; // last active item in array, record matching of
current char sequence
int j=0; // index used in str2
stack schar;
for(int i=0; i
{
schar.push(str1[i]);
if(str1[i] == str2[j])
{
(*(pMatchArray+last))++;
if((++j)==len2) //match found for whole str2
{
//remove str2 from current pos;
for(int itmp=0; itmp
schar.pop();
*(pMatchArray+last) = -1;
if (last == 0)
j=0;
else
{
j = *(pMatchArray+(--last));
j++;
}
}
}
else if(str1[i] == str2[0])
{
last++;
*(pMatchArray+last) = 0;
j=1;
}
else
{
while(last>=0)
*(pMatchArray+(last--)) = 0;
last = 0;
j = 0;
}
}
while(!schar.empty())
{
cout << schar.top();
schar.pop();
}
return 0;
} |
h**********d
发帖数: 4313 | 4 楼主的题目貌似不是删除连续substring把，不过那貌似更简单些 |
m**q
发帖数: 189 | 5 这个题目是删除所有a，b，c的occurrence么？
还是只删除按顺序出现的abc？
前者的话，两个指针，做in-place deletion就行了，O(n)
【在 j**y 的大作中提到】
: 不能用java的function
: aababccbc remove abc 最后应该""
: 有啥思路？多谢
|
l*****g
发帖数: 685 | 6 他的意思应该是recursively删除出现的abc, 到最后不出现abc为止
你说得对，这题用两个指针in-place做就可以了，不需要用额外的stack或者array
不过对lz的原题，O(n)是不够的。假如要删除的pattern的长度是m, worst case，譬如
acccccccc, 需要O(m*n)；不过，如果m长度固定或很小，可以认为是 O(n)
【在 m**q 的大作中提到】
: 这个题目是删除所有a，b，c的occurrence么？
: 还是只删除按顺序出现的abc？
: 前者的话，两个指针，做in-place deletion就行了，O(n)
|
l*****g
发帖数: 685 | 7 用C++写了一个版本:
void RecursivelyRemoveSubString(char *str, const char *sub)
{
if (!str || !sub || *sub == 0 || *str == 0 || strlen(str) < strlen(sub))
return;
char *end = str;
char *cur = str;
int subLen = strlen(sub);
char subEnd = sub[subLen - 1];
while (*cur != 0)
{
*end = *cur;
if (*end == subEnd)
{
char *reCur = end;
int subIndex = subLen - 1;
bool match = true;
bool reCurEnd = false;
while (!reCurEnd && subIndex >= 0)
{
if (reCur == str)
reCurEnd = true;
if (*reCur == sub[subIndex])
{
reCur--;
subIndex--;
}
else
{
match = false;
break;
}
}
if (match && subIndex < 0)
end = reCur;
}
cur++; end++;
}
*end = 0;
}
【在 l*****g 的大作中提到】
: 他的意思应该是recursively删除出现的abc, 到最后不出现abc为止
: 你说得对，这题用两个指针in-place做就可以了，不需要用额外的stack或者array
: 不过对lz的原题，O(n)是不够的。假如要删除的pattern的长度是m, worst case，譬如
: acccccccc, 需要O(m*n)；不过，如果m长度固定或很小，可以认为是 O(n)
|
g***s
发帖数: 3811 | 8 Even if m is not very small, there is O(n) algorithm.
【在 l*****g 的大作中提到】
: 他的意思应该是recursively删除出现的abc, 到最后不出现abc为止
: 你说得对，这题用两个指针in-place做就可以了，不需要用额外的stack或者array
: 不过对lz的原题，O(n)是不够的。假如要删除的pattern的长度是m, worst case，譬如
: acccccccc, 需要O(m*n)；不过，如果m长度固定或很小，可以认为是 O(n)
|
l*****g
发帖数: 685 | 9 你是对的
如果m是变量，那O(mn)就不能简化成O(n)
【在 g***s 的大作中提到】
: Even if m is not very small, there is O(n) algorithm.
|
g***s
发帖数: 3811 | 10 I meant, there is a algorithm in O(n) instead of O(m*n).
【在 l*****g 的大作中提到】
: 你是对的
: 如果m是变量，那O(mn)就不能简化成O(n)
|
|
|
l*****g
发帖数: 685 | 11 请zkss, 先谢过
【在 g***s 的大作中提到】
: I meant, there is a algorithm in O(n) instead of O(m*n).
|
h**********d
发帖数: 4313 | 12 请问in-place怎么O(n)？不是O(m*n)?
两个指针，做in-place deletion就行了，O(n)
【在 m**q 的大作中提到】
: 这个题目是删除所有a，b，c的occurrence么？
: 还是只删除按顺序出现的abc？
: 前者的话，两个指针，做in-place deletion就行了，O(n)
|
t*****s
发帖数: 416 | 13 如果能用O(n)空间的话似乎确实可以用O(n)时间完成。
顺序读取的过程中遇到匹配串就开始顺序编号，比如
abababccccccc
编号为
1212123333333
一旦读到匹配串的终结字符就检查上一个编号是不是m-1
如果是就删除当前字符和之前m-1个字符。 |
t*****s
发帖数: 416 | 14
漏说了，非顺序出现的匹配串字符或者不匹配字符一律编为0
【在 t*****s 的大作中提到】
: 如果能用O(n)空间的话似乎确实可以用O(n)时间完成。
: 顺序读取的过程中遇到匹配串就开始顺序编号，比如
: abababccccccc
: 编号为
: 1212123333333
: 一旦读到匹配串的终结字符就检查上一个编号是不是m-1
: 如果是就删除当前字符和之前m-1个字符。
|
t*****s
发帖数: 416 | 15 嗯，这个不对，见笑了，大家继续
【在 t*****s 的大作中提到】
:
: 漏说了，非顺序出现的匹配串字符或者不匹配字符一律编为0
|
g***s
发帖数: 3811 | 16 you assumed there are no duplicate chars in the sub string.
If so, your algo can just be changed a little to make it work. Also, no need extra space.
【在 t*****s 的大作中提到】
: 如果能用O(n)空间的话似乎确实可以用O(n)时间完成。
: 顺序读取的过程中遇到匹配串就开始顺序编号，比如
: abababccccccc
: 编号为
: 1212123333333
: 一旦读到匹配串的终结字符就检查上一个编号是不是m-1
: 如果是就删除当前字符和之前m-1个字符。
|
t*****s
发帖数: 416 | 17 删除后将编号状态机set到剩余的前一个字符的状态，即如果前一个字符是a，那么下一
个读取字符如果
是b就编号为2而非0。
这样应该可以。
【在 t*****s 的大作中提到】
: 嗯，这个不对，见笑了，大家继续
|
t*****s
发帖数: 416 | 18 确实没考虑连续重复字符的情况。KMP的具体算法记不清了，还得回去好好复习去。
need extra space.
【在 g***s 的大作中提到】
: you assumed there are no duplicate chars in the sub string.
: If so, your algo can just be changed a little to make it work. Also, no need extra space.
|
g***s
发帖数: 3811 | 19 Based on KMP
请zkss, 先谢过
★ Sent from iPhone App: iReader Mitbbs 6.81 - iPhone Lite
【在 l*****g 的大作中提到】
: 请zkss, 先谢过
|
t*****s
发帖数: 416 | 20 拿一个栈把所有的match break点压栈，匹配-删除到最后了再一个一个读回来重新比较？
【在 g***s 的大作中提到】
: Based on KMP
:
: 请zkss, 先谢过
: ★ Sent from iPhone App: iReader Mitbbs 6.81 - iPhone Lite
|
|
|
l*****g
发帖数: 685 | 21 KMP是用于找出所有matches in one traveral of the string
譬如，从 abcdabcaabcbc 里找abc, 用 KMP 就可以找出 3 matches
LZ的问题是：找出match, 删除，再在结果里找match, 再删除，直到结果里无match为止
过程如下：
input: abcdabcaabcbc
find matches: [abc]d[abc]a[abc]bc
delete matches: dabc
find matches again: d[abc]
delete matches: d
no more match
output: d
这儿recursively地做了两次find-->delete；如果把KMP用于每一次recursion, 单个
recursion的复杂度是 O(n), 但多个recursion的总的复杂度还是会累加
【在 g***s 的大作中提到】
: Based on KMP
:
: 请zkss, 先谢过
: ★ Sent from iPhone App: iReader Mitbbs 6.81 - iPhone Lite
|
g**e
发帖数: 6127 | 22 this is O(nm)
较？
【在 t*****s 的大作中提到】
: 拿一个栈把所有的match break点压栈，匹配-删除到最后了再一个一个读回来重新比较？
|
g**e
发帖数: 6127 | 23 不需要recursive，只需要根据automata回到上一个position，每个元素最多访问两次
，所以是O(n)
我想grass应该是这个意思
为止
【在 l*****g 的大作中提到】
: KMP是用于找出所有matches in one traveral of the string
: 譬如，从 abcdabcaabcbc 里找abc, 用 KMP 就可以找出 3 matches
: LZ的问题是：找出match, 删除，再在结果里找match, 再删除，直到结果里无match为止
: 过程如下：
: input: abcdabcaabcbc
: find matches: [abc]d[abc]a[abc]bc
: delete matches: dabc
: find matches again: d[abc]
: delete matches: d
: no more match
|
g***s
发帖数: 3811 | 24 删除以后，回到当前位置-m。重新计算这m个元素的跳转位置 O(m)
那么每次删除m个元素，我们需要额外的O(m)时间。
最多可以删除n个元素，所以最多额外用O(n）的时间。
【在 g**e 的大作中提到】
: 不需要recursive，只需要根据automata回到上一个position，每个元素最多访问两次
: ，所以是O(n)
: 我想grass应该是这个意思
:
: 为止
|
c*********t
发帖数: 2921 | 25 能不能解释一下什么是in-place deletion？
能给个一般的例子吗？不一定要用lz的题目为例。
谢谢！
【在 m**q 的大作中提到】
: 这个题目是删除所有a，b，c的occurrence么？
: 还是只删除按顺序出现的abc？
: 前者的话，两个指针，做in-place deletion就行了，O(n)
|
g**e
发帖数: 6127 | 26 O(n) time, O(1) space based on KMP. Here I used an utility ArrayList but it
can be removed to do in-place.
public static void recursiveDelete(String target, String pattern) {
if (target == null || pattern == null || pattern.length() ==
0
|| target.length() == 0)
return;
// convert target string into a ArrayList of char
ArrayList charset = new ArrayList();
for (char c : target.toCharArray()) {
charset.add(c);
}
printArray(charset);
// get KMP automata for pattern
int[] overlap = getOverlap(pattern);
int i = 0, j = 0;
while (i
while(true) {
if (i>=0 && j>=0 && charset.get(i) ==
pattern.charAt(j)) {
j++;
if (j == pattern.length()) {
System.out.print(" -> ");
//delete pattern from target
while(j>0) {
charset.remove(i--);
j--;
}
printArray(charset);
//j = 0; //reset j; this is
unnecessary as j=0 after the loop
i -= pattern.length(); //
retrogress m positions
}
break;
} else if (j == 0){
break;
} else
j = overlap[j];
}
i++;
}
}
private static void printArray(List ca) {
for (char c : ca) {
System.out.print(c);
}
}
/**
* build automata for pattern p based on KMP, O(n)
*/
private static int[] getOverlap(String p) {
if (p.length() == 0)
return null;
int[] o = new int[p.length()];
o[0] = -1;
for (int i = 1; i < p.length(); i++) {
o[i] = o[i - 1] + 1;
while (o[i] > 0 && p.charAt(i-1) != p.charAt(o[i] -
1))
o[i] = o[o[i] - 1] + 1;
}
o[0] = 0;
return o;
}
两次
【在 g***s 的大作中提到】
: 删除以后，回到当前位置-m。重新计算这m个元素的跳转位置 O(m)
: 那么每次删除m个元素，我们需要额外的O(m)时间。
: 最多可以删除n个元素，所以最多额外用O(n）的时间。
|
l*****g
发帖数: 685 | 27 别计较maxq说的 in-place deletion， 不是什么正规定义
他意思应该是指 in-place algorithm
因为这个algorithm 用于做 deletion, 所以随口说了 in-place deletion
【在 c*********t 的大作中提到】
: 能不能解释一下什么是in-place deletion？
: 能给个一般的例子吗？不一定要用lz的题目为例。
: 谢谢！
|
c*********t
发帖数: 2921 | 28 到底这个题目问的是哪种情形：
1. 是删除单个的 a, b, c吗？
还是
2. 删除连续出现的‘abc’?
谢谢！
【在 j**y 的大作中提到】
: 不能用java的function
: aababccbc remove abc 最后应该""
: 有啥思路？多谢
|
s*****n
发帖数: 5488 | 29 二楼的说的很好啊。用stack
string removeSubstringRecursively(string s, string matchString){
struct stackElement{
char s,
int index,
}
Stack stack= new Stack();
int index = 0;
foreach (char c in s) {
if (matchString[index] == c){
stack.push(c,index++);
if (index == matchString.Length){
for( int i = 0; i < index ; i++)
stack.Pop();
index = stack.peek().index;
}
}
else{
index = (c = matchstring[0] ? 0, -1);
stack.push(c, index);
}
}
StringBuilder sb = new StringBuilder (stack.Count);
for( int i = 0; i < stack.Count; i++){
sb.append(stack.pop().s);
}
return sb.Reverse();
} |
s****y
发帖数: 1 | 30 不用栈应该也可以吧
bool isMatch(const std::string &str,const std::string &pattern,int loc){
int i = pattern.size()-1;
while( i >= 0){
if(pattern[i--] != str[loc--])
return false;
}
return true;
}
void removeStringPattern(std::string &str, const std::string & pattern){
if( str.empty() || pattern.empty() || str.size() < pattern.size())
return;
int patternSize = pattern.size();
int strSize = str.size();
int loc = 0;
while(strSize >= patternSize && loc < strSize){
if(pattern[patternSize-1]==str[loc] && isMatch(str,pattern,loc)){
str.erase(loc-patternSize+1, patternSize);
loc -= patternSize -1;
strSize -= patternSize;
}
else
loc++;
}
} |
