TWOSTRS - Editorial

editorial
, , , , , ,
32

Ohhk I understood why aho is better for choice here.

Like here we have somewhat similar question to this:
Find all occurrences in T of any pattern in
the set of patterns P = {P1, . . . , Pz}.

We can do it naive way by using kmp Z time.
So its computation time becomes O(|T|*Z).
whereas, aho can do it in linear time.

Thanks for this question and editorial :slight_smile:

33

Yes, Aho-Corasick is like a kmp on a trie.

2 Likes
34

This problems has a tight time limit, so that similar algos that differ just a little bit can get TLE.

35

Can someone help me out with my implimentation of following problem. It shows wrong answer but I could’nt find any.

https://www.codechef.com/viewsolution/33002794

36

Your idea looks good. So you need to optimize your code.

  • Don’t use long longs if it is not necessary.
  • Don’t do a lot of push_back or emplace_back. Use arrays instead.
  • You can save automaton nodes corresponding to prefixes of A, so you don’t need this for:
for 
for(i = max(pa - K + 1, 0ll); i <= pa; i++) {
  v = t[v].go[a[i] - 'a'];
}

Here is your optimized solution.

1 Like
37

Try this test:

Test 
1
abc
def
3
d 100
bcef 51
ce 50

The correct answer is 101.

38

yup I have applied gfg approch and got tle

39

Whoa! how did you do that! I could never think of those nasty little optimizations!
So, let me guess, compiler works faster with smaller data types because it has to allocate smaller chunks of bytes which it finds easily in the memory, right?
Likewise, if we use arrays, compiler doesn’t have to reallocate the chunks again and again searching all over in the memory, right?
Thank you!

40

The Same problem , I was also getting.This can be optimized with aho-corasick algorithm.

41

@sharepo Thanks for the explanation. The step 3 in your explanation intends to count the sum of beauties of all occurrences of strings from S in the suffix B[i…∣B∣−1]. I think it should be noted that your implementation additionally counts the sum of beauties of any string from S that ends in the suffix B[i…∣B∣−1] but doesn’t start in it. This works because whenever you have to use the value of suffBSum[i], you would have most definitely included the previous 25 characters before i. Thus, all strings from S that end in the suffix B[i…∣B∣−1] also need to be counted.

42

Thankyou! @sharepo
How could I miss that…
But that explains my last two days of codechef long XD

43

Thanks, fixed.

44

can someone please find error in my implementation. My code is based on editorial. I tried my best to find but could not do it. Please Help

code

45

The setter’s solution is so simple and clear.
I have commented what I have understood. Just posting here so that it will be helpful for someone. Kindly please point out if there are any misunderstanding.

https://www.codechef.com/viewsolution/33075686

3 Likes
46

The error is in calculating suf_sum array.

Change this 
rep(i,0,sr)
{
	ll cur = 0;
	rep(j,i,sr)
	{
		cur = go(cur,r[j]-'a');
		suf_sum[i]+=process_node(cur);
	}
}
to this 
rep(i,0,sr)
{
	last = go(last,r[i]-'a');
	suf_sum[i]+=process_node(last);
}
for (int i = sr - 2; i >= 0; i--) suf_sum[i] += suf_sum[i + 1];

similar to my slution.

1 Like
47

Thanks for the reply man. and yeah you are correct, I got AC after that change and also understood what was wrong with my code. Thanks

48

https://www.codechef.com/viewsolution/33113113

can someone please have a look at my code and point out the mistake? I computed the prefSum and SuffixSum arrays. then i am adding pref[i-25] and suff[j+25]. from (i-24) to (j+24) , i am moving along the automaton.

49

Have a look at this comment above.

50

i did, the test is not working. i have not accounted for substrings inside the set S. thanks for pointing out

51

for(k=1; k<=25; k++){

    for(i=0; i<=(int)B.length()-k; i++){
        struct Node *node = A_trie.get_node(B, i+k-1, k, -1);

        for(j=0; j<A.length(); j++){
            bridge_answers[j][i] += A_trie.get_value(node, A, j, min(26-k, 12), -1);
        }
    }
}

why dont we run 1st loop from k=14. stucked in this logic for few days.