I solve this problem with complexity O(N*6). I use DP.
The inner cycle with complexity O(6) (heh, it's not correct
notation but...) is checking for finding words.
I read the input with cin.get(ch). And i use cin.ignore to
skip characters when i know that this is not "dialogue".

Is there real linear time solution?