সোমবার, ৩ জুন, ২০১৯

UVA 10100 - Longest Match

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string a, b;
    int t = 0;
    while (getline(cin, a))
    {
        t++;
        getline(cin, b);
        if (a.length() == 0 || b.length() == 0)
            printf("%2d. Blank!\n", t);
        else
        {
            for (int i = 0; i < a.length(); i++)
                if (!(a[i] >= 'A' && a[i] <= 'Z' || a[i] >= 'a' && a[i] <= 'z' || a[i] >= '0' && a[i] <= '9'))
                    a[i] = ' ';
            for (int i = 0; i < b.length(); i++)
                if (!(b[i] >= 'A' && b[i] <= 'Z' || b[i] >= 'a' && b[i] <= 'z' || b[i] >= '0' && b[i] <= '9'))
                    b[i] = ' ';
            string c[501], d[501];
            istringstream strma(a);
            int n = 1;
            while (strma >> c[n])
                n++;
            istringstream strmb(b);
            int m = 1;
            while (strmb >> d[m])
                m++;
            int T[501][501];
            for (int j = 0; j < m; j++)
                T[0][j] = 0;
            for (int i = 1; i < n; i++)
            {
                T[i][0] = 0;
                for (int j = 1; j < m; j++)
                    if (c[i] == d[j])
                    {
                        T[i][j] = T[i - 1][j - 1] + 1;
                    }

                    else
                        T[i][j] = max(T[i - 1][j], T[i][j - 1]);
            }
            printf("%2d. Length of longest match: %d\n", t, T[n - 1][m - 1]);
        }
    }
    return 0;
}

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন

Factorization with prime Sieve

vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); ...