daily pastebin goal
54%
SHARE
TWEET

Untitled

a guest Mar 26th, 2019 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class nwp {
  2.     String s1;
  3.     String s2;
  4.     int[][] tab;
  5.     int dlugosc=0;
  6.     public nwp(String s1, String s2) {
  7.         this.s1 = s1;
  8.         this.s2 = s2;
  9.          this.tab = new int[s1.length()][s2.length()];
  10.          generate();
  11.     }
  12.     private void generate(){
  13.         for(int i=0;i<s1.length();i++){
  14.             for(int j=0;j<s2.length();j++){
  15.                 if(s1.charAt(i) == s2.charAt(j)){
  16.                     if(i>0&&j>0)tab[i][j] = tab[i-1][j-1]+1;
  17.                     else tab[i][j]= 1;
  18.                 }else{
  19.                     if(i>0&&j>0)tab[i][j]= Math.max(tab[i-1][j],tab[i][j-1]);
  20.                     else if(i>0&&j<=0)tab[i][j]= Math.max(tab[i-1][j],0);
  21.                     else if(i<=0&&j>0)tab[i][j]= Math.max(0,tab[i][j-1]);
  22.                 }
  23.             }
  24.         }
  25.     }
  26.     public void print(){
  27.         System.out.print("\nWyglad Tablicy:\n  ");
  28.         for (int x=0;x<s2.length();x++){
  29.             System.out.print(s2.charAt(x) + " ");
  30.         }
  31.         System.out.println("");
  32.         for(int i=0;i<s1.length();i++){
  33.             System.out.print(s1.charAt(i) + " ");
  34.             for(int j=0;j<s2.length();j++){
  35.                 System.out.print(tab[i][j] + " ");
  36.             }
  37.             System.out.println("");
  38.         }
  39.         getNWP();
  40.     }
  41.     private void getNWP(){
  42.         dlugosc = tab[s1.length()-1][s2.length()-1];
  43.         int x=s1.length()-1;
  44.         int y=s2.length()-1;
  45.         String nwp = "";
  46.         int i=0;
  47.         System.out.println(dlugosc);
  48.         boolean done=false;
  49.         int iloscZakretow=0;
  50.         int[][] zakret = new int[Math.max(s1.length(),s2.length())][Math.max(s1.length(),s2.length())];
  51.         while(done==false){
  52.         //gurwaaaa
  53.             if(x !=0 && y != 0) {
  54.                 if (tab[x][y] > Math.max(tab[x - 1][y], tab[x][y - 1])) {
  55.                     nwp = nwp + s1.charAt(x);
  56.                     x = x - 1;
  57.                     y = y - 1;
  58.                 } else if (tab[x][y] == tab[x - 1][y] && tab[x][y] != tab[x][y - 1]) {
  59.                     x = x - 1;
  60.                 } else if (tab[x][y] == tab[x][y - 1] && tab[x][y] != tab[x - 1][y]) {
  61.                     y = y - 1;
  62.                 } else {
  63.                     y = y - 1;
  64.                 }
  65.             }if(x==0 && y==0)nwp = nwp + s1.charAt(x);
  66.             else if(y==0 && tab[x-1][y]==tab[x][y])x--;
  67.             else if(y ==0 && tab[x-1][y] < tab[x][y]){
  68.                 nwp = nwp + s1.charAt(x);
  69.             }
  70.             else if(x==0 && tab[x][y-1]==tab[x][y])y--;
  71.             else if(x==0 && tab[x][y-1] < tab[x][y]){
  72.                 nwp = nwp + s1.charAt(x);
  73.             }
  74.  
  75.             if(nwp.length()==dlugosc){
  76.                 System.out.println(reverseString(nwp));
  77.                 break;
  78.  
  79.             }
  80.         }
  81.     }
  82.     private String reverseString(String x){
  83.         int dl = x.length();
  84.         String reversed = "";
  85.         for(int i=dlugosc-1;i>=0;i--){
  86.             reversed = reversed + x.charAt(i);
  87.         }
  88.         return reversed;
  89.     };
  90. }
  91.  
  92. public class Main {
  93.  
  94.     public static void main(String[] args) {
  95.         nwp m = new nwp("ffbbd","dbbff");
  96.         m.print();
  97.     }
  98. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top