Thanks for the reply. It took me a while to reply back because I had to do an insane amount of debugging lol. Every small test I did was giving me the right answer and the smallest one that failed on the official test cases was big.

Turns out I was doing mask |= (1<<fileNum), but using unsigned long long, changing to (1ULL<<fileNum) fixed it.

I don't get why though. It was putting a lot of other 'on' bits on some states, but shouldn't the signed bit affect only the 64th one? (I never use the 64th, cause F<=60).

Moreover, as far as I understand, any shift should shift the 64th away (except for fileNum 0, which didn't give me any problems at all...). What was the problem in this case?

My solution ended up being:

• Build automaton for A$B!C#...
• Run each string A, B, C, ... separately and mark the masks (instead of running the full A$B!C#... string and marking according to the index, like I was doing before)
• Do a dfs to mark which states are reachable (don't go on with it if there is a '$' transition)
• For reachable states, count the number of different masks

Dunno if any of this made a difference or if it was the 1ULL problem all this time, will revert to the previous solution later and see what happens.

But wouldn't this be the same (timewise)?

Let's say the constant amount of work you do (inserting the masks, comparing lengths, etc) = T and the other constant work = K.

Doing it the way you're saying is N*(T+K). But doing the dfs later would be N*K + N*T, which is essentially the same (plz correct me if I'm wrong).

It may make the code shorter though (mine is already too big haha), so I'll do it to see what happens :D

Suppose you have the automaton for the full string "word1$word2#word3%..." with each sate also pointing to its suffix parent (also called suffix pointer, parent pointer, etc), you can add a new property "mask" to each state (a bitmsk representing the set of words searchable by the substrings represented by that state).

To calculate the masks, you can run the full string in the automaton and for each state you reach you add that word to the set (mask) and propagate it to its suffix parent until you reach the root. (Skipping the end of word symbols, since they aren't a part of any actual word).

Something like this:

currentState = root
fullString = "word1$word2#word3%..."
currentWord = 0

for each currentChar in fullString {
    currentState = the state reached by currentState using transition currentChar;
    if (currentChar is an end-of-word symbol [$, #, %, ...]) {
      //means we've reached the end of the current word and are going to the next
      ++currentWord;
    } else {
       auxState = currentState;
       while (auxState != root) { // propagate while we don't reach the root
           auxState.mask = (1LL<<currentWord); // Turn on the bit referent to the current word in that state
           auxState = auxState.suffixParent;
       }
    }
}

For solving with a Suffix Array, I think you can use something like this:

If you have the LCP array, you can derive the "searchable suffix sets" in a way that for each index i, there's a set from [beg+1, ..., i, ..., end-1] where beg it's the first index to the left where lcp[idx] < lcp[i] and end is the first index to the right where that happens.

You can kinda consider the LCP a histogram where each set is a contiguous part on the x axis in that histogram. Then you need to find which words appear in that suffix set to find the actual set.

Example:

lcp: 1 2 3 4 3 1 2 0 1
idx: 0 1 2 3 4 5 6 7 8

You can search the suffixes represented by indexes 0 to 6, 1 to 4, 2 to 4, 3, 6, 8. Then for each of these you need to see the set of words represented by it, that will be a searchable subset.