Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class nwp {
- String s1;
- String s2;
- int[][] tab;
- int dlugosc=0;
- public nwp(String s1, String s2) {
- this.s1 = s1;
- this.s2 = s2;
- this.tab = new int[s1.length()][s2.length()];
- generate();
- }
- private void generate(){
- for(int i=0;i<s1.length();i++){
- for(int j=0;j<s2.length();j++){
- if(s1.charAt(i) == s2.charAt(j)){
- if(i>0&&j>0)tab[i][j] = tab[i-1][j-1]+1;
- else tab[i][j]= 1;
- }else{
- if(i>0&&j>0)tab[i][j]= Math.max(tab[i-1][j],tab[i][j-1]);
- else if(i>0&&j<=0)tab[i][j]= Math.max(tab[i-1][j],0);
- else if(i<=0&&j>0)tab[i][j]= Math.max(0,tab[i][j-1]);
- }
- }
- }
- }
- public void print(){
- System.out.print("\nWyglad Tablicy:\n ");
- for (int x=0;x<s2.length();x++){
- System.out.print(s2.charAt(x) + " ");
- }
- System.out.println("");
- for(int i=0;i<s1.length();i++){
- System.out.print(s1.charAt(i) + " ");
- for(int j=0;j<s2.length();j++){
- System.out.print(tab[i][j] + " ");
- }
- System.out.println("");
- }
- getNWP();
- }
- private void getNWP(){
- dlugosc = tab[s1.length()-1][s2.length()-1];
- int x=s1.length()-1;
- int y=s2.length()-1;
- String nwp = "";
- int i=0;
- System.out.println(dlugosc);
- boolean done=false;
- int iloscZakretow=0;
- int[][] zakret = new int[Math.max(s1.length(),s2.length())][Math.max(s1.length(),s2.length())];
- while(done==false){
- //gurwaaaa
- if(x !=0 && y != 0) {
- if (tab[x][y] > Math.max(tab[x - 1][y], tab[x][y - 1])) {
- nwp = nwp + s1.charAt(x);
- x = x - 1;
- y = y - 1;
- } else if (tab[x][y] == tab[x - 1][y] && tab[x][y] != tab[x][y - 1]) {
- x = x - 1;
- } else if (tab[x][y] == tab[x][y - 1] && tab[x][y] != tab[x - 1][y]) {
- y = y - 1;
- } else {
- y = y - 1;
- }
- }if(x==0 && y==0)nwp = nwp + s1.charAt(x);
- else if(y==0 && tab[x-1][y]==tab[x][y])x--;
- else if(y ==0 && tab[x-1][y] < tab[x][y]){
- nwp = nwp + s1.charAt(x);
- }
- else if(x==0 && tab[x][y-1]==tab[x][y])y--;
- else if(x==0 && tab[x][y-1] < tab[x][y]){
- nwp = nwp + s1.charAt(x);
- }
- if(nwp.length()==dlugosc){
- System.out.println(reverseString(nwp));
- break;
- }
- }
- }
- private String reverseString(String x){
- int dl = x.length();
- String reversed = "";
- for(int i=dlugosc-1;i>=0;i--){
- reversed = reversed + x.charAt(i);
- }
- return reversed;
- };
- }
- public class Main {
- public static void main(String[] args) {
- nwp m = new nwp("ffbbd","dbbff");
- m.print();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement