Zaplatany warunek zadania

0

Cześć! :)

Pokładam nadzieję w waszej pomocy.
Mam problem algorytmiczny z programowania. Dość oczywiste jest, że tutaj trzeba opierać się algorytmie Knutha-Pratta-Morissa. Jednak zadanie jest trochę utrudnione, zastępując klasyczny sposób porównywanie symboli, którego sensu ja nie łapię. :(

Oto warunek:

łańcuchy znaków składają się z dwóch nieprzecinających się zestawów symboli R1 i R2. Dwa łańcuchi symboli są uważane za równe, jeśli istnieje bijekcja z R1 do R2, po użyciu której na pierwszym łańcuchu otrzymujemy drugi.

Dane łańcuchy S i Z (szablon).
Opierając się na danym określeniu równości symboli, trzeba wyznaczyć ile symboli łańcuchu S jest Z odpowiednikami.

Input:
Dane N i M. (1 <= N,M < 52).
W drugiej linijce N symbli R1 zestawu.
W 3 lin. M symboli R2 zestawu.
4 lin. dana S
5 lin. dana Z
R1 i R2 może składać się tylko z małych i wielkich lotyńskich liter.
S i Z długoście nie przewyszają 100000.

Oto mój kod zródłowy (zgaduję, że tylko z powodu złego porównywania on nabiera 23%):

 
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int Max = 52;

int CharConvertToInt(char);
int prefixFunc(string,int);
bool Equall(char,char);

int n,m;
string a;                              // Pagalbine eilute
vector<bool> R1(Max,0);
vector<bool> R2(Max,0);
string S,Z;

int main()
{
    cin >> n >> m;

    // Aibes R1 apdorojimas
    cin >> a;
    for (size_t i = 0; i < a.size(); ++i)
      R1[CharConvertToInt(a[i])] = 1;

    // Aibes R2 apdorojimas
    cin >> a;
    for (size_t i = 0; i < a.size(); ++i)
      R2[CharConvertToInt(a[i])] = 1;

    cin >> S >> Z;
    int kk = (int) Z.length();
    Z += S;

    cout << prefixFunc(Z,kk) << endl;

}

int prefixFunc(string s, int k)
{
   int res = 0;
   int n = (int) s.length();
   vector<int> pi(n,0);

   for (int i = 1; i < n; ++i)
   {
      int j = pi[i-1];
      while (j > 0 && !Equall(s[i],s[j]))
         j = pi[j-1];
      if (Equall(s[i],s[j])) ++j;
      pi[i] = j;
      //cout << "i " << i << " " << pi[i] << " " << k << endl;
      if (pi[i] == k && i > k)  res += k;
   }

  // cout << "pi \n";
  // for (int i = 0; i < n; ++i)
   //   cout << i << " " << pi[i] << endl;

   return res;
}

bool Equall(char a, char b)
{
   int aa = CharConvertToInt(a);
   int bb = CharConvertToInt(b);
  // cout << "a " << a << " " << "b " << b << endl;
   //cout << R2[aa] << " " << R2[bb] << endl;
   if (R2[aa])
      return (a == b ? true : false);
   else
      return (R2[bb] == 1 ? true : false);
}

// char i int nuo 0 iki 51
int CharConvertToInt(char a)
{
   if (a > 64 && a < 91)
      return (int(a)-65);
   else
      return (int(a)-71);
}

Jakie kto ma pomysły jak te porównywanie wykonać? :)

0

Czy u kogos jest idea jak po innemu wykonac funkcje Equall?

0

No ja rozumiem ze ta bijekcja ma się opierać na tym że literki są równe gdy:
R1[literka] = literka_w_R2 taka że R2[literka_w_R2] = literka

1 użytkowników online, w tym zalogowanych: 0, gości: 1