Thread: Faster way of deleting characters

How "slow" is it now?
How did you measure it?
How much "faster" does it need to be for success?
Which OS/Compiler are you using?
Did you try using the compiler optimisation flags?

1. I don’t know how much it is slow. Well it's just too slow.
2. I'm testing this program on a special website, which has its own input and only rates that the output is correct and gives the time relative to 1s, it's exactly shows achieved time if its less than 1s, or writes that is greater than 1s.
3. All solutions should be given in less than 1s.
4. At home, I'm using CodeBlocks, but I think it doesn't make any difference, because on this site probably it's different.
5. No, I didn’t tried.

The problem is that for the first 4 tests, the result is very good (the largest achieved time is ~ 0.05s), the fifth test doesn't want to pass because of exceeding the time limit.

I had some ideas to solve this problem, but in practice I only tested find_first_of(), function which turn out too slow. I don't see solution of this problem in checking individual letters, but in searching the whole subsequence and removing them. My another problem is that I'm not sure how it should look like now in the final code. LCS algorithm, it requires unfortunately too much of memory.

Based on what I see you trying to do, wouldn't you 'have' to check every letter considering the string could be anything? Try building with optimization. In Code::Blocks, it even says [faster code, even faster code, etc] next to each optim. choice.

If your program isn't accepted by one of those online judges due to time restrictions, then by far the most likely answer is that you're using the wrong algorithm.
Standard library functions are only slow if you're using them poorly, or for the wrong purpose, or the wrong functions.

Give details on the problem you are solving, perferably linking to it, and then either describe your solution in sufficient detail or provide code.

Ok. So this is how my solution of this problem looks:

Until j is less than lenght of str2 do :
1) Positions of letter from str1 in string str2 assign to p (p=str1.find_first_of(str1[j])
2) If letter occuring then i'm removing it from str2, if not then I'm adding it to a previously created variable s3 (if(p<0) s3.push_back(str1[i]); else str2.erase(p,1);)
At the end I'm write out s3.

I tried different solutions. I searched letters from string str2 in str1 and then if they appeared program deleting them and at the end show str1.
I could see that in 4/5 cases (also when my program can't past the test) str1 is longer than str2.
So it seems weird that algorithm presentated above is faster than this another one where from str1 I throw out one after another all letters from str2.
I also tried use array which can automatically adding another letter to s3 without checking that this letter appears in str2, but this solution turned out slower than this which I wrote above.
It's really hard for me find another alternative solution expect of this where from str1 I thorow out all the common subsequences from str2, but I don't know how to write it in a final code.

Originally Posted by paut

Numbers of bits in char? It shouldn't be 8?

Yes, but in theory (and historically), a byte might not be 8 bits. Besides, even if a byte was guaranteed to be 8 bits, it is better to use a named constant than a magic number.

The length of str2_letters has nothing to do with the length of str2. The length is simply the number of possible characters in
the alphabet used to build str2. In this case, a character is a single 8-bit byte = 1<< 8 = 256 possible character values.

You index into str2_letters using a character value. For example str2_letters['s'] == 0 means there's no character s anywhere in str2. Likewise, if str2_letters['s'] == 1, then there is an s in str2. Relate this to my pseudo-code by seeing that str1[i] or str2[i] is the character at index i in each string.

Code:

For (i=0; i<len.str2; i++) str2_letters=1;  <- I said to set str2_letters[str2[i]] =1 ... this is different from setting str2_letters = 1 (the latter being illegal in C++)
 String s3;
 For (i=0; i<len.str1; i++)  <- I don't think this is how you get the length of a string
 IF (str2_letters[i]) str2_letters.erase(tab.begin() + i -1);  <--- i isn't the character at index i in str1.  It's just i. And you can't call erase() on an array.  And what's tab in this context?
 Else
 S3.Push_back(str2_letters[i]);