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ć? :)