Return information from a String

A very simple way to do this is with replace.

String troca[][] = {{"<R1>","João Pedro"},{"<R2>", "Maria"}, {"<R3>", "Joaquina Fofa"}};
String FraseParametro = "<R1> casou com <R2>, e traiu ela com <R3>.";
System.out.println(FraseParametro);
for(int i = 0;i<troca.length;i++)
    FraseParametro = FraseParametro.replace(troca[i][0], troca[i][1]);
System.out.println(FraseParametro);

Try instead to replace what you have for a marker. That's all you need.

String FraseParametro[] = {"casou com",", e traiu ela com"};
String Frase = "João Pedro casou com Maria, e traiu ela com Joaquina Fofa.";
for(int i = 0;i<FraseParametro.length;i++)
    Frase = Frase.replace(FraseParametro[i],";");

System.out.println(Frase);

String[] teste = Frase.split(";");
for(int i = 0;i<teste.length;i++)
    System.out.printf("\nIndice %s - Valor: %s",i,teste[i].trim());

Possible solution:

public class App {

private List<String> keys;
private String fraseParametro;
private String frase;
private Map<String, String> map;

public App() {
    keys = new ArrayList<>();
    map = new HashMap<>();
}

public static void main( String[] args ) throws IOException, InterruptedException {
    String fraseParametro = "<R1> casou com <R2>, e traiu ela com <R3>.";

    String frase = "João Pedro casou com Maria, e traiu ela com Joaquina Fofa.";

    App app = new App();
    app.addKey("<R3>");
    app.addKey("<R1>");
    app.addKey("<R2>");

    app.setFrase(frase);
    app.setFraseParametro(fraseParametro);
    app.createPairKeyValue();
    Map<String, String> keyValue = app.getMap();
    System.out.printf("Frase Parâmetro: %s\n", app.getFraseParametro());
    System.out.printf("Frase: %s\n", app.getFrase());
    for (String key : keyValue.keySet()) {
        System.out.printf("%s: %s\n", key, keyValue.get(key));
    }

}

public void createPairKeyValue() {
    Collections.sort(keys);

    String findingSubstitues = frase;
    for (String key : keys) {
        String replacement = findValue(findingSubstitues, key);
        if (replacement != null) {
            map.put(key, replacement);
            findingSubstitues = findingSubstitues.replaceAll(replacement, key);
        }
    }
}

public Map<String, String> getMap() {
    return this.map;
}

private String findValue(String phrase, String key) {
    List<String> phraseWithKeys = getWords(fraseParametro);
    List<String> phraseWithoutKeys = getWords(phrase);
    int index = phraseWithKeys.indexOf(key);

    if (index == -1) {
        return null;
    }

    String replacement = phraseWithoutKeys.get(index);

    for (int i = index+1; i < phraseWithoutKeys.size(); ++i) {
        if (((index+1) == phraseWithKeys.size()) || !phraseWithoutKeys.get(i).equals(phraseWithKeys.get(index+1))) {
            replacement += " " + phraseWithoutKeys.get(i);
        } else {
            break;
        }
    }
    return replacement;
}

public void addKey(String key) {
    keys.add(key);
}

public void setFraseParametro(String fraseParametro) {
    this.fraseParametro = fraseParametro;
}

public void setFrase(String frase) {
    this.frase = frase;
}

public List<String> getWords(String phrase) {
    String[] words = phrase.split(" |,|\.");
    return Arrays.asList(words);
}

public String getFraseParametro() {
    return fraseParametro;
}

public String getFrase() {
    return frase;
}

}