Odpowiedz 
 
Ocena wątku:
  • 0 Głosów - 0 Średnio
  • 1
  • 2
  • 3
  • 4
  • 5
Problem z algorytmem Sundaya'a na 2 znaki
03-24-2015, 05:51 PM (Ten post był ostatnio modyfikowany: 03-24-2015 05:56 PM przez lolo.)
Post: #1
Problem z algorytmem Sundaya'a na 2 znaki
Witam, mam pewien problem z ww algorytmem. Algorytm wygląda na dobrze napisanego ale w pewnym momencie wybiega poza zakres o 1 index i nie mam pojęcia dlaczego. Dziękuje za pomoc
Pozdrawiam
public class Sunday2 extends StringSearch
{
        List<Integer> List1 = new ArrayList<>();
    public Sunday2(String text, String pattern)
    {
        super(text,pattern);
    }
   
    public List<Integer> Sunday2search()
    {
        List<List<Integer>> W = new ArrayList<>();
        
         int m= pattern.length();
	 int n= text.length();
         
         for(int i = 0; i <= 256; i++)
         {
                    
             for(int j = 0; j <= 256; j++)
             {
                 List1.add(j,-2);
                 
             }
             W.add(i , List1);    
         }
         
    
         for(int j = 0; j <= 256; j++) 
         {
             
             W.get(j).set(pattern.charAt(0), -1);
         }
	for(int i = 0; i <= m; i++) //w tym miejscu występuje problem
            
        {
            W.get(pattern.charAt(i)).set(pattern.charAt(i+1), i);
                     
        }
           
	for(int j = 0; j < 256; j++) 
        {
            W.get(pattern.charAt(m - 1)).set(j, m - 1);
        }
            
            for(int i = 0 ; i < n - m; i = i + m - W.get(text.charAt(i+1)).get(pattern.charAt(i+2)))
    {
        
		if(i >= n - m)
                {
                    break;
                }
                
        if(matchesat(i)) 
        {
            List1.add(i);
        }
            
    }

    

        for(int w : List1)
        {
            JOptionPane.showMessageDialog(null, "Ilosc wystapein: " + w);
        }
           return List1;

    }
}
Znajdź wszystkie posty użytkownika
Odpowiedz cytując ten post
03-24-2015, 06:06 PM
Post: #2
RE: Problem z algorytmem Sundaya'a na 2 znaki
Przecież sam wskazałeś, gdzie Ci wychodzi poza zakres więc sprawdzenie dlaczego w tym miejscu o 1 wychodzi poza zakres nie jest trudne. Kilka linii wyżej do zmiennej m (swoją drogą zacznij lepiej nazywać zmienne) długość stringa a indeksacja jest od 0 więc w linii:
for(int i = 0; i <= m; i++)
powinieneś dać:
for(int i = 0; i < m; i++)

GG: 2802571
Znajdź wszystkie posty użytkownika
Odpowiedz cytując ten post
03-24-2015, 06:14 PM
Post: #3
RE: Problem z algorytmem Sundaya'a na 2 znaki
Zmienne są nazwane. W ten sposób co napisałeś też wcześniej próbowałem i nic nie pomaga dalej wyskakuje poza zakres.
Znajdź wszystkie posty użytkownika
Odpowiedz cytując ten post
03-24-2015, 06:41 PM
Post: #4
RE: Problem z algorytmem Sundaya'a na 2 znaki
W linii 36 masz: W.get(pattern.charAt(i)).set(pattern.charAt(i + 1), i);
Czyli gdy i == pattern.length();
To w .set() pobierasz z pattern znak który znajduje się o 1 dalej niż ma pattern.

GG: 2802571
Znajdź wszystkie posty użytkownika
Odpowiedz cytując ten post
03-24-2015, 07:06 PM
Post: #5
RE: Problem z algorytmem Sundaya'a na 2 znaki
(03-24-2015 06:41 PM)lolo napisał(a):  W linii 36 masz: W.get(pattern.charAt(i)).set(pattern.charAt(i + 1), i);
Czyli gdy i == pattern.length();
To w .set() pobierasz z pattern znak który znajduje się o 1 dalej niż ma pattern.

Rozumiem ale usuwając tą jedynkę i zapisując
for(int i = 0; i < m; i++)
{
W.get(pattern.charAt(i)).set(pattern.charAt(i), i);
}
Również wybiega poza zakres.
Robiąc to w ten sposób
for(int i = 0; i < m - 1; i++)
{
W.get(pattern.charAt(i)).set(pattern.charAt(i), i);
}
Już nie wybiega poza zakres ale nie znajduję wzorca w tekście.
Pozdrawiam
Znajdź wszystkie posty użytkownika
Odpowiedz cytując ten post
03-24-2015, 07:17 PM
Post: #6
RE: Problem z algorytmem Sundaya'a na 2 znaki
Teoretycznie przy zapisie
for(int i = 0; i < m; i++)
{
W.get(pattern.charAt(i)).set(pattern.charAt(i), i);
}
nie powinno wychodzić poza zakres bo i maksymalnie może dojść do pattern.length()-1.
Ciężko mi coś więcej wywnioskować z tego kodu.

GG: 2802571
Znajdź wszystkie posty użytkownika
Odpowiedz cytując ten post
03-24-2015, 10:12 PM
Post: #7
RE: Problem z algorytmem Sundaya'a na 2 znaki
(03-24-2015 07:17 PM)lolo napisał(a):  Teoretycznie przy zapisie
for(int i = 0; i < m; i++)
{
W.get(pattern.charAt(i)).set(pattern.charAt(i), i);
}
nie powinno wychodzić poza zakres bo i maksymalnie może dojść do pattern.length()-1.
Ciężko mi coś więcej wywnioskować z tego kodu.

Właśnie nie powinien i już nie mam pomysłu jak to ugryźć. Jeżeli ma Pan ochotę zerknąć na cały program to mogę podesłać.
Pozdrawiam
Znajdź wszystkie posty użytkownika
Odpowiedz cytując ten post
Odpowiedz 


Skocz do:


Użytkownicy przeglądający ten wątek: 1 gości