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.