leven2

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package pal;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author pc404
 */
public class SearchText {

    private int N;
    private int M;
    private int cI;
    private int cD;
    private int cR;
    private String P;
    private String T;
    private String actStr;
    private char actChar;
    BufferedReader reader;
    private String line;
    private String[] spLine;
    private int index, endLength, dist;
    private int[][] levenstein;
    private char a;
    private int min;
    private int act;
    private boolean isUnderMin;

    public SearchText() {
        try {
            // TODO code application logic here
            reader = new BufferedReader(new InputStreamReader(System.in));
            //reader = new BufferedReader(new FileReader("pub02.in"));
            line = reader.readLine();
            spLine = line.split(" ");
            N = Integer.parseInt(spLine[0]);
            M = Integer.parseInt(spLine[1]);
            cI = Integer.parseInt(spLine[2]);
            cD = Integer.parseInt(spLine[3]);
            cR = Integer.parseInt(spLine[4]);
            T = reader.readLine();
            P = reader.readLine();
            index = -1;
            endLength = -1;
            dist = Integer.MAX_VALUE;
            levenstein = new int[N + 1][M + 1];
            for (int i = 0; i < levenstein.length; i++) {
                levenstein[i][0] = i * cI;
            }
            for (int k = 1; k < levenstein[0].length; k++) {
                levenstein[0][k] = k * cD;
            }
            for (int j = 0; j < N; j++) {
                for (int i = 1; i <= N - j; i++) {
                    actChar = T.charAt(i + j - 1);
                    countDistance(actChar, i);
                    if (isUnderMin == false) {
                        break;
                    }
                    act = levenstein[i][M];
                    if (act < dist) {
                        dist = act;
                        index = j;
                        endLength = i;
                    } else if (act == dist) {
                        if (i < endLength) {
                            index = j;
                            endLength = i;
                        } else if (i == endLength) {
                            if (j < index) {
                                index = j;
                            }
                        }
                    }
                }
            }
            System.out.println(index + " " + endLength + " " + dist);
        } catch (IOException ioe) {
            Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ioe);
        }
    }

    private void countDistance(char a, int i) {
        isUnderMin = false;
        for (int j = 1; j <= M; j++) {
            if (a == P.charAt(j - 1)) {
                min = levenstein[i - 1][j - 1];
            } else {
                min = levenstein[i - 1][j - 1] + cR;
            }
            if (levenstein[i][j - 1] + cD < min) {
                min = levenstein[i][j - 1] + cD;
            }
            if (levenstein[i - 1][j] + cI < min) {
                min = levenstein[i - 1][j] + cI;
            }
            levenstein[i][j] = min;
            if (levenstein[i][j] < dist) {
                isUnderMin = true;
            }
            //System.out.print(levenstein[i][j] + " ");
        }
    }
}