Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.4 kB
1
Indexable
Never
 static boolean verifyPattern(String p, String t, int sti) {
		
		for(int i=0;i<p.length();i++) {
			if(p.charAt(i)!=t.charAt(i+sti)) {
				return false;
			}
		}
		
		return true;
	}
    
    ArrayList<Integer> search(String pattern, String text)
    {
    
        // Multiplication factor constant
		int d = 29;
		
		// Largest prime number for modulo
		int q = 101;
		
		ArrayList<Integer> res = new ArrayList<>();
		
		if(pattern.length() == 0 || text.length() == 0 || text.length() < pattern.length()) {
			res.add(-1);
			return res;
		}
		
		
		int pValue = 0;
		int tValue = 0;
		
	    int h = 1;
		for (int i = 0; i < pattern.length() - 1; i++)
            h = (h * d) % q;
		
		// Hash of pattern and text
		for(int i=0;i<pattern.length();i++) {
			pValue = (pValue*d + pattern.charAt(i))%q;
			tValue = (tValue*d + text.charAt(i))%q;
		}
		
		int i;
		// Rolling hash and comparison
		for(i=pattern.length();i<text.length();i++) {
			
			if(pValue == tValue) {
				if(verifyPattern(pattern,text,i-pattern.length())) {
					res.add(i-pattern.length()+1);
				}
			}
			
			tValue = ((tValue - text.charAt(i-pattern.length())*h)*d + text.charAt(i))%q;
			if (tValue < 0)
				tValue = (tValue + q);
		}
		
		if(pValue == tValue) {
				if(verifyPattern(pattern,text,i-pattern.length())) {
					res.add(i-pattern.length()+1);
				}
			}
		
		if (res.size() == 0) {
		    res.add(-1);
		}
		return res;
		
    }