Tävlingsprogrammering/Uppgifter/Rövarspråket

Lösning

Det finns giriga lösningar som löser problemet i linjär tid, men i det här fallet duger en körtid på O(|A||B|) där |A| och |B| är längden på de två indatasträngarna.

Vi betraktar problemet som en grafproblem, där vi har precis en nod för varje par av positioner i de två strängarna. För varje nod (i, j) så kan vi gå till två andra potentiella noder:

1) Vi går ett steg framåt i båda strängarna, dvs till (i+1, j+1). Det här går dock bara om A[i] == B[j].

2) Vi går ett steg framåt i den övre strängen tre steg framåt i den nedre strängen, dvs till (i+1, j+3). Detta går dock bara om A[i] == B[j], B[j+1] == ‘o’, B[j] == B[j+2] och A[i] är en konsonant (och därmed är också B[j] en konsonant).

Vi börjar i noden (0,0), och vi frågar oss om noden (|A|, |B|) går att nå. Detta kan vi ta reda på genom att göra en djupet- eller breddenförst-sökning. Notera att om vi når en position som vi redan har besökt så kan vi omedelbart avbryta sökningen (detta är viktigt, programmet får annars en exponentiell körtid).

Lösning i Java av Erik Odenman:

import java.util.*;
import java.io.*;
 
public class RovarSpraket {
    
        static int n, m;
        static char[] start, goal;
        static boolean[][] visited;
        
        public static void main(String[] args) throws IOException {
                BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
                PrintWriter out = new PrintWriter(System.out);
                
                start = in.readLine().toCharArray();
                goal = in.readLine().toCharArray();
                n = start.length;
                m = goal.length;
                visited = new boolean[n+1][m+1];
                dfs(0, 0);
                out.println(visited[n][m] ? "ja" : "nej");
                
                in.close();
                out.close();
        }
        
        static boolean isConsonant(char c) {
                return !"aeiouy".contains(c+"");
        }
        
        static void dfs(int p1, int p2) {
                if (visited[p1][p2]) return;
                visited[p1][p2] = true;
                if (p1 < n && p2 < m) {
                        if (start[p1] == goal[p2]) {
                                dfs(p1+1, p2+1);
                                if (p2 + 2 < m && isConsonant(goal[p2]) && goal[p2+1] == 'o' && goal[p2+2] == goal[p2]) {
                                        dfs(p1+1, p2+3);
                                }
                        }
                }
        }
}

Som sagt fanns det även en girig algoritm, som löser problemet i linjär tid, beroende av strängarnas längd. Där går man bara igenom strängarna parallellt och fortsätter så länge bokstäverna är samma. Då man stöter på en konsonant finns det möjlighet att den bokstaven är översatt till rövarspråk. Då räknar man hur många gånger den konsonanten upprepas för de båda strängarna, med kravet att bokstaven 'o' ska skilja upprepningarna åt. Om det är färre upprepningar för översättningen än för originalsträngen, eller att det är mer än dubbelt så många upprepningar hos översättningen, kan inte översättningen komma från den potentiella originalsträngen. Om man sedan når strängarnas slut är översättningen möjlig, annars inte.

Lösning i linjär tid, skriven i C++:

#include <iostream>
using namespace std;
 
const string vowels = "aeiouy";
 
int main(){
    string o, t;
    cin >> o;
    cin >> t;
    
    int i = 0, j = 0;
    while (i < o.size() && j < t.size() && o[i] == t[j]) {
        if (vowels.find(o[i]) == string::npos){ // Om det är en konsonant:
            int a = 1, b = 1;
            while(i+2 < o.size() && o[i+1] == 'o' && o[i+2] == o[i]){ // Om nästa bokstav är 'o' och den därefter är samma konsonant som den aktuella
                i += 2;
                a++;
            }
            while(j+2 < t.size() && t[j+1] == 'o' && t[j+2] == t[j]){ // Samma while-sats som ovan, men med den andra strängen
                j += 2;
                b++;
            }
            if (a > b || 2*a < b){
                break;
            }
        }
        j++;
        i++;
    }
    if (j == t.size() && i == o.size()){ // Om man nått slutet utan några problem
        cout << "ja";
    }
    else {
        cout << "nej";
    }
    return 0;
}