I'm extremely sorry for late publication.
Complexity: O(1).
Author of the idea: Vladik.
Worked on the problem: Vladik.
Complexity: O(n2). Author of the idea: MikeMirzayanov.
Worked on the problem: MikeMirzayanov.
Complexity: O(n3 * m).
Author of the idea: altruist.
Worked on the problem: Vladik.
Complexity: O(n).
** Author of the idea:** altruist.
** Worked on the problem:** altruist.
Complexity: O(n).
** Author of the idea:** MikeMirzayanov.
** Worked on the problem:** altruist.
Complexity: O(d * (N * M + K)), where d — alphabet power.
** Author of the idea:** Vladik.
** Worked on the problem:** Vladik.