Algorytm sprawdzający ilość liter zgadzających się z inną zmienną string

0

prosiłbym was o pomoc, bo sam nie mam pojęcia jak to zrobić.

słuchajcie. mam przykładowo dwie zmienne string o różnych łańcuchach znaków. jak sprawdzić zatem, ile liter zgadza sie w jednej ze zmiennych z druga zmienna.

np.
zmienna string o wartości "pole" i zmienna string o wartości "bolek". System powinien obliczyć, i przedstawić liczbowo, ze wartosc "pole" ma 3 wspolne litery z wartoscia "bolek".

Dziekuję z góry!

0

Pokaż co masz, jak zobaczymy że się starasz to pomożemy.

Albo: Podaj ile jesteś w stanie dać.

0

A jaka powinna być odpowiedź dla "lama" i 'mleka"? (Litera "a" jest w obu słowach, różna jest krotność występowania.)

0

payl

nie, przysięgam że próbowałem ale... no.. nie potrafię!

znam pętle for, znam funkcję lenght, wiem że trzeba zliczać i kiedy, próbowałem ze static_cast (czyli funkcja lenght. --> ze stringiem PojedynczyZnak przez static_)cast na char i porównywać) ale nie działa...

0
function EditDistance(s, t: ansistring): double;
  var
    d : array of array of integer;
    i,j,cost : integer;
  begin
    if (length(s)=0)and(length(t)=0) then exit(0.0);
    {
    Compute the edit-distance between two strings.
    Algorithm and description may be found at either of these two links:
    http://en.wikipedia.org/wiki/Levenshtein_distance
    http://www.google.com/search?q=Levenshtein+distance
    }

    try
      //initialize our cost array
      SetLength(d,Length(s)+1);
      for i := Low(d) to High(d) do begin
        SetLength(d[i],Length(t)+1);
      end;

      for i := Low(d) to High(d) do begin
        d[i,0] := i;
        for j := Low(d[i]) to High(d[i]) do begin
          d[0,j] := j;
        end;
      end;

      //store our costs in a 2-d grid
      for i := Low(d)+1 to High(d) do begin
        for j := Low(d[i])+1 to High(d[i]) do begin
          if s[i] = t[j] then begin
            cost := 0;
          end
          else begin
            cost := 1;
          end;

          //to use "Min", add "Math" to your uses clause!
          d[i,j] := Min(Min(
                     d[i-1,j]+1,      //deletion
                     d[i,j-1]+1),     //insertion
                     d[i-1,j-1]+cost  //substitution
                     );
        end;  //for j
      end;  //for i

      //now that we've stored the costs, return the final one
      Result := d[Length(s),Length(t)];
    finally
      //cleanup
      for i := Low(d) to High(d) do begin
        for j := Low(d[i]) to High(d[i]) do begin
          SetLength(d[i],0);
        end;  //for j
      end;  //for i
      SetLength(d,0);
    end;  //try-finally
    result:=max(length(s),length(t))-result;
    result:=result/max(length(s),length(t));
  end;

Zadowolony? No to super.

0

a takie coś?

#include <iostream>
#include <conio.h>
#include <string>

using namespace std;

int main()
{
    char chZnak;
    unsigned uIlosc, uIlosc2, z, i, j;
    string strTekst, strTekst2;
    for ( x = 1; x < 24; ++x)
    {
        if (x = 1) chZnak = 'a';if (x = 7) chZnak = 'g';if (x = 13) chZnak = 'm';if (x = 19) chZnak = 't';
        if (x = 2) chZnak = 'b';if (x = 8) chZnak = 'h';if (x = 14) chZnak = 'n';if (x = 20) chZnak = 'u';
        if (x = 3) chZnak = 'c';if (x = 9) chZnak = 'i';if (x = 15) chZnak = 'o';if (x = 21) chZnak = 'w';
        if (x = 4) chZnak = 'd';if (x = 10) chZnak = 'j';if (x = 16) chZnak = 'p';if (x = 22) chZnak = 'z';
        if (x = 5) chZnak = 'e';if (x = 11) chZnak = 'k';if (x = 17) chZnak = 'r';if (x = 23) chZnak = 'y';
        if (x = 6) chZnak = 'f';if (x = 12) chZnak = 'l';if (x = 18) chZnak = 's';
        
         uIlosc = 0 ;
         for ( i = 0 ; i <= strTekst.length() - 1 ; ++i)
         {
             uIlosc2 = 0 ;
             for ( j = 0 ; j <= strTekst2.length() - 1 ; ++j)
             {
                 if (strTekst[i] == strTekst2[j]) uIlosc += 1;
             }
         }
         
    }
         
         
}
0

nie chce działać.
mimo iż dodałem na początku i końcu jakiś komunikat wyświetla się tylko ten początkowy i potem nic nie idzie dalej.

oj, sorki payl. nie zauważyłem twojego postu.
a co do kodu to nie chce się twój skompilować.

1

a co do kodu to nie chce się twój skompilować.

Ubolewam nad tym iż nie masz możliwości dania kodów diagnostycznych kompilatora wobec czego nigdy nie rozwiążemy Twojego problemu. Do zobaczenia w następnym wcieleniu.

EDIT:
A TY W OGÓLE POWIEDZIAŁEŚ JAKI KOMPILATOR? BO JEST WIĘCEJ NIŻ JEDEN. cholera, znowu flamuje.

0

A czy tu przypadkiem nie chodzi o zwykłą intersekcję, gdzie kolejność liter nie ma znaczenia?

"pole" ∩ "bolek" = {'e', 'l', 'o'}
"dupa" ∩ "papier" = {'a', 'p'}

itp.

0

A moze chodzi o Odległość Levenshteina?

0

No, z tego... kodu..., który wątkotwórca podał wyżej wynika, że jednak chodzi o prostą intersekcję.
W takim razie algorytm jest banalny. Podpowiedzi dla wątkotwórcy:

  1. Najpierw usuń duplikaty z wzorca, potem jedź po kolei. Niestety nie wiem dokładnie co chcesz osiągnąć, gdyż w pytaniu niby chcesz tylko listować wspólne znaki, ale później w kodzie je zliczasz (czy ilość jest znacząca?).
  2. Użyj tablicy, nie musi ona być tak duża żeby pomieścić wszystkie litery alfabetu (wystarczy to, co masz we wzorcu).
  3. Mapuj. Tablica wyników i tablica znaków są... no cóż... tablicami.
  4. Twój algorytm jest "prawie" dobry, ale napisz go od początku.

Spróbuj coś wykombinować i pokaż co wyszło.

2

ponieważ nie jest sprecyzowany język oto gotowiec w c#. należy się piwo.

using System;

class Program
{
	static void Main(string[] args)
	{
		string s1 = "dolina".ToLower(), s2 = "dyplomata".ToLower();
		byte[] counters = new byte['z' - 'a'];

		for (int i = 0; i < s1.Length; i++)
			if (s1[i] >= 'a' && s1[i] <= 'z')
				counters[s1[i]-'a'] = 1;

		for (int i = 0; i < s2.Length; i++)
			if (s2[i] >= 'a' && s2[i] <= 'z' && counters[s2[i]-'a'] == 1)
				counters[s2[i]-'a'] = 2;

		for (int i = 0; i < counters.Length; i++)
			if (counters[i] == 2)
				Console.Write((char)(i+'a'));
		
		Console.WriteLine();
	}
}
0
ŁF napisał(a)

ponieważ nie jest sprecyzowany język oto gotowiec w c#. należy się piwo.

To jest bardzo zły i niechlujny algorytm.
Po pierwsze, alokujesz tablicę dla wszystkich liter, co jest bez sensu. Alokuj tylko dla tych, które się pojawiają we wzorcu.
Po drugie, intersekcję robisz na podstawie tego, czy w tablicy liczników danej literze przyporządkowana jest liczba 2, czyli pojawiła się co najmniej jeden raz w obu ciągach. Nie zrozum mnie źle, ale to dość prymitywne rozwiązanie.
Po trzecie, jedziesz po obu ciągach, co jest niepotrzebne.
Po czwarte, jedziesz po całych ciągach, co przy długich danych wejściowych jest bezsensem.

Propozycja w języku C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int  qschrcmp(const void  *left, const void  *right)
{
    if ( *(char*)left == *(char*)right )
        return 0;
    else
        return *(char*)left > *(char*)right ? 1 : -1;
}


static size_t  struniq(char  *buf)
{
    char        pch = 0;
    size_t      pos = 0, offset = 0;


    do {
        if ( buf[pos] == pch )
            offset++;
        else
            buf[pos - offset] = buf[pos];
        pch = buf[pos];
        pos++;
    } while ( pch > 0 );

    return pos - offset - 1;
}


int  main(int  argc, const char  *argv[])
{
    size_t          needles_len, haystack_len, i, j;
    char            *needles;
    unsigned long   *counts;


    if ( argc < 3 ) {
        fprintf(stderr, "Usage:  %s needles haystack\n", argv[0]);
        return 1;
    };

    needles = strdup(argv[1]);

    needles_len = strlen(argv[1]);
    haystack_len = strlen(argv[2]);

    qsort(needles, needles_len, 1, qschrcmp);
    needles_len = struniq(needles);

    if ( (counts = (unsigned long*)calloc(sizeof(unsigned long), needles_len)) == NULL ) {
        fprintf(stderr, "Buy more RAM\n");
        return 2;
    };

    for ( i = 0; i < haystack_len; i++ )
        for ( j = 0; j < needles_len; j++ )
            if ( argv[2][i] == needles[j] )
                counts[j] += 1;

    for ( j = 0; j < needles_len; j++ )
        if ( counts[j] )
            fprintf(stdout, "%c - %li\n", needles[j], counts[j]);

    free(needles);
    free(counts);
    return 0;
}
2
Kumashiro napisał(a)

Algorytm ŁF jest jak testowanie znaku liczby poprzez konwersję do stringa i sprawdzenie pierwszego znaku
oszty! a Twój jak strzelanie z lasera do muchy, kiedy można ją ubić gazetą.

moje kilka linijek ma być skuteczne i jak najprostsze, ale i tak się wybronią.

Kumashiro napisał(a)

Po pierwsze, alokujesz tablicę dla wszystkich liter, co jest bez sensu. Alokuj tylko dla tych, które się pojawiają we wzorcu.
po co? używam rozwiązania adekwatnego do problemu. liter jest kilkadziesiąt, znaków góra tyle, co w utf16. tablica odpowiadająca wielkością wszystkim możliwym rozwiązaniom jest tutaj niczym superszybka hashmapa - a jednocześnie ma wystarczająco mały rozmiar. pod terminem "wystarczająco" rozumiem, że program działa na w miarę współczesnym pececie, gdzie kilkadziesiąt bajtów to tyle, co nic. zdaję sobie sprawę, że istnieją systemy, gdzie kilkadziesiąt bajtów to cała dostępna pamięć, jednak rozwiązania tego typu to na naszym forum rzadkość, dlatego zakładam, że o taki system nie chodzi. nie jest to również część klasy mogącej występować w nieokreślonej, dowolnie dużej ilości kopii - i dlatego powstał akurat taki kod.
zresztą optymalizacja pod względem zużycia pamięci często wiąże się ze słabszą wydajnością algorytmu i tak właśnie jest z Twoim (pętla w pętli + qsort).

Kumashiro napisał(a)

Po drugie, intersekcję robisz na podstawie tego, czy w tablicy liczników danej literze przyporządkowana jest liczba 2, czyli pojawiła się co najmniej jeden raz w obu ciągach. Nie zrozum mnie źle, ale to dość prymitywne rozwiązanie.
czy możesz uzasadnić swoją opinię? działa przecież tak samo jak Twoje, tylko nie zwiększam licznika, bo w zadaniu nie ma o tym mowy. użyłem dwójki zamiast stałej, bo zadanie jest banalne i nie ma sensu komplikować go stałymi. to w pełni świadome rozwiązanie. przerobienie z 2 na inkrementację to zmiana kilku liter, uwzględniając poprawkę przy wypisywaniu wyniku - ale ponownie, nie jest to treścią zadania.

Kumashiro napisał(a)

Po trzecie, jedziesz po obu ciągach, co jest niepotrzebne.
robisz prawie to samo, i to jeszcze w zagnieżdżonej pętli. ja mam liniową złożoność O(m+n+26)=>O(m+n), Ty masz optymistyczne O(nlogn + ml + n) => O(nlogn+m), gdzie l = ilość unikalnych elementów, pesymistycznie kwadratową O(nn + ml + n)=>O(n(m+n)). dla każdej kombinacji długości ciągów mój algorytm (i to w wersji bez optymalizacji z następnego cytatu) będzie szybszy, przy czym odbywa się to kosztem niecałych kilkudziesięciu bajtów pamięci więcej.

Kumashiro napisał(a)

Po czwarte, jedziesz po całych ciągach, co przy długich danych wejściowych jest bezsensem.
celna uwaga. sprawdzenie, czy tablica jest wypełniona jedynkami/dwójkami byłoby super optymalizacją, łatwą a bardzo przyspieszającą przy długich ciągach, ale... nie chce mi się.
z kolei w Twojej wersji i tak jedziesz po wszystkich. najpierw qsort jedzie po wszystkich elementach pierwszej tablicy, potem zagnieżdżona pętla po wszystkich elementach drugiej tablicy. i co najciekawsze - nie masz jak tego uniknąć. ja mam.

i wreszcie - mój kod jest znacznie krótszy, przez co bardziej przejrzysty. zgadzam się, jest mniej elastyczny - nie poradzi sobie bez przeróbek z literami spoza przedziału 'a'..'z', ale cóż, coś za coś - Twój kod ma też swoje zalety :-)

[dopisane]
a jednak mi się zachciało.

class Program
{
	static void Main(string[] args)
	{
		const char startLetter = '0', stopLetter = 'ż';
		const string s1 = "1adfApDolinauZ", s2 = "2sDue3zpA";

		byte[] counters = new byte[stopLetter - startLetter + 1];
		int index, count = 0;

		for (int i = 0; i < s1.Length; i++)
		{
			index = s1[i] - startLetter;
			if (index >= 0 && index < counters.Length && counters[index] == 0)
			{
				counters[index]++;
				if (++count >= counters.Length) break;
			}
		}

		count = 0;
		for (int i = 0; i < s2.Length; i++)
		{
			index = s2[i] - startLetter;
			if (index >= 0 && index < counters.Length && counters[index] == 1)
			{
				counters[index]++;
				System.Console.Write(s2[i]);
				if (++count >= counters.Length) break;
			}
		}


		System.Console.WriteLine();
		System.Console.ReadKey();
	}
}
1

Teraz ja, teraz ja!

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>

typedef std::unordered_map<char, int> intersection_map;

intersection_map string_intersection(std::string s1, std::string s2) {
  std::sort(s1.begin(), s1.end());
  std::sort(s2.begin(), s2.end());
  
  std::string result(std::min(s1.length(), s2.length()), ' ');
  
  std::string::iterator pos = std::set_intersection(s1.begin(), s1.end(),
                                                    s2.begin(), s2.end(),
                                                    result.begin());
  result.erase(pos, result.end());

  intersection_map result_map;

  for (char c : result) {
    result_map[c]++;
  }

  return result_map;
}

int main() {
  std::string s1("ala ma kota kota ma ala");
  std::string s2("janek tez ma kota i raka");

  intersection_map result = string_intersection(s1, s2);

  for (auto pair : result) {
    std::cout << pair.first << "-" << pair.second << std::endl;
  }

  return 0;
}

Złożoność - dwa sorty, trzy iteracje i jeszcze hash mapa! (3.2 GHz, -O2, gcc 4.6.1, 1000000x = 1.26 sekundy, chociaż to jest pewnie niemiarodajne)

Wynik dla tych danych z kodu:

 -5
a-5
k-2
m-1
o-1
t-2

Wynik jest inny niż w kodzie wyżej, ponieważ robię część wspólną. I tak nie wiadomo o co chodziło autorowi. :-)

A tutaj taki na wzór ŁF:

std::string string_intersection2(std::string s1, std::string s2) {
  std::string result;
  result.reserve(std::min(s1.length(), s2.length()));

  // tu sobie mozna zmieniac :-P
  const char start_char = 0;
  const char stop_char = 127;

  std::vector<int> char_lut(stop_char - start_char + 1, 0);

  for (char c : s1) {
    char_lut[c - start_char] = 1;
  }

  for (char c : s2) {
    const char index = c - start_char;
    if (char_lut[index] == 1) {
      char_lut[index] = 2;
      result += c;
    }
  }

  return result;
}

Haha, zabawa nie ma końca. Tutaj taki na wzór ŁF, który liczy jak mój pierwszy i jest szybszy ale nie tak wygodny:

std::vector<int> string_intersection3(std::string s1, std::string s2) {
  const char start_char = 0;
  const char stop_char = 127;
  const size_t count = stop_char - start_char + 1;
  
  std::vector<int> char_hist1(count + 1, 0);
  std::vector<int> char_hist2(count + 1, 0);

  for (char c : s1) {
    char_hist1[c - start_char]++;
  }

  for (char c : s2) {
    char_hist2[c - start_char]++;
  }

  std::vector<int> result(count + 1, 0);

  for (size_t i = 0; i < count; ++i) {
    if (char_hist1[i] > 0 && char_hist2[i] > 0) {
      result[i] = std::min(char_hist1[i], char_hist2[i]);
    }
  }

  return result;
}

Do wyboru do koloru w 3 językach. :-)

0
class String
  def intersect(string)
    self.split(//).sort & string.split(//).sort
  end
end
 
puts "abba".intersect("ab").join(" ,")

Jeśli ma być jednokrotnie to jeszcze dodać unique.

0
ŁF napisał(a)

czy możesz uzasadnić swoją opinię? działa przecież tak samo jak Twoje, tylko nie zwiększam licznika, bo w zadaniu nie ma o tym mowy. użyłem dwójki zamiast stałej, bo zadanie jest banalne i nie ma sensu komplikować go stałymi. to w pełni świadome rozwiązanie. przerobienie z 2 na inkrementację to zmiana kilku liter, uwzględniając poprawkę przy wypisywaniu wyniku - ale ponownie, nie jest to treścią zadania.

Nie, nie chodzi mi o stałe itp. Jeśli jednak wynika to z celowego uproszczenia algorytmu, to spox. Sama treść zadania jest niejasna. Nie wiadomo zbytnio co dokładnie ma być robione, a wątkotwórca milczy, więc robimy różne warianty... chociaż teraz to tylko dla czystej zabawy.

ŁF napisał(a)
Kumashiro napisał(a)

Po trzecie, jedziesz po obu ciągach, co jest niepotrzebne.
robisz prawie to samo, i to jeszcze w zagnieżdżonej pętli.

Mój kod nie jest alternatywą dla Twojego, gdyż robi co innego :)

ŁF napisał(a)

Twój kod ma też swoje zalety :-)

Każdy kod ma jakieś zalety, a im więcej przykładów, tym więcej możliwości wyboru :)

Anyway, w komentarzach już przeprosiłem za zbyt pochopne naskoczenie na Ciebie personalnie oraz odwołałem swoją paplaninę. Jeśli się spotkamy, możesz mnie kopnąć w dupę za nadgorliwość (albo postawię Ci piwo). Następnym razem postaram się, żeby mój zły humor nie miał wpływu na wygłaszane przeze mnie opinie.

0

W Pythonie jest zbyt prosto:

set("dolina").intersection(set("dyplomata"))
0
"dolina" intersect "dyplomata" distinct /* <- poprawka */

Kurde ;/

0

dziękuję za taką ilość odp.
chodziło mi nie o podanie, ile i jakie litery sie zgadzaja, a ogólną liczbę zgadzających się liter.
zna ktoś grę fallout 3?
tam przy hackowaniu kompa było właśnie to o co mi chodzi.

0

To to co ja podałem tylko piszesz:

puts "pole".intersect("bolek").size
0

chodzi mi o C++.

0

Dostałeś już rozwiązanie, weź przykład z std::set_intersection. Funkcja ta zwraca iterator na koniec tego przecięcia. Odejmij od tego iterator na początek i to będzie twój wynik.

0

Dodam jeszcze jedną rzecz: jeżeli on chce napisać odpowiednik hackowania z Fallout 3 to ten algorytm ma sprawdzać czy te same litery znajdują się na odpowiadających pozycjach. Przykład: abcdefg i cbqaeqi. Wynik: 2, bo tylko 'b' na drugiej pozycji i 'e' na piątej się zgadzają.

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