Facebook
From TajnePrzezPoufne, 2 Months ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 49
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6.  
  7. namespace NWP
  8. {
  9.     class Program
  10.     {
  11.         static void NWP(String A, String B, int m, int n)
  12.         {
  13.             int[,] N = new int[m + 1, n + 1];
  14.  
  15.             for (int i = 0; i <= m; i++)
  16.             {
  17.                 for (int j = 0; j <= n; j++)
  18.                 {
  19.                     if (i == 0 || j == 0)
  20.                         N[i, j] = 0;
  21.                     else if (A[i - 1] == B[j - 1])
  22.                         N[i, j] = N[i - 1, j - 1] + 1;
  23.                     else
  24.                         N[i, j] = Math.Max(N[i - 1, j], N[i, j - 1]);
  25.                 }
  26.  
  27.             }
  28.  
  29.             int index = N[m, n];
  30.             int temp = index;
  31.  
  32.             char[] nwp = new char[index + 1];
  33.  
  34.             nwp[index] = '\0';
  35.  
  36.  
  37.             int k = m, l = n;
  38.  
  39.             while (k > 0 && l > 0)
  40.             {
  41.                 if (A[k - 1] == B[l - 1])
  42.                 {
  43.                     nwp[index - 1] = A[k - 1];
  44.                     k--;
  45.                     l--;
  46.                     index--;
  47.                 }
  48.                 else if (N[k - 1, l] > N[k, l - 1])
  49.                     k--;
  50.                 else
  51.                     l--;
  52.             }
  53.  
  54.             Console.Write("Najdluzszy wspolny podciag " + A + " i " + B + " to: ");
  55.             for (int q = 0; q <= temp; q++)
  56.                 Console.Write(nwp[q]);
  57.         }
  58.  
  59.  
  60.         public static void Main()
  61.         {
  62.             String A = "Alibaba";
  63.             String B = "Aliexpres";
  64.             int m = A.Length;
  65.             int n = B.Length;
  66.             NWP(A, B, m, n);
  67.             Console.ReadLine();
  68.         }
  69.     }
  70. }