Cod sursa(job #1420258)

Utilizator ibicecIT Zilla ibicec Data 18 aprilie 2015 00:01:51
Problema Potrivirea sirurilor Scor 40
Compilator java Status done
Runda Arhiva educationala Marime 2.43 kb
import java.util.*;
import java.io.*;


public class Main {
	
	public static final int RADIX = 129;
	public static final int MOD = 99997;

	public static int charToNum(char c) {
		if ( Character.isDigit(c) ) {
			return c-'0';
		} else if ( Character.isUpperCase(c) ) {
			return c-'A'+10;
		} else if ( Character.isLowerCase(c) ) {
			return c-'a'+10+26;
		}
		
		throw new IllegalArgumentException("Only alphanumeric symbols are allowed");
	}
	
	public static int hash(char[] charArray, int len) {
		int h = 0;
		for (int i=0; i<len; i++) {
			if ( Character.isLetterOrDigit(charArray[i]) ) {
				h = (RADIX * h + charArray[i]) % MOD;
			} else {
				throw new IllegalArgumentException("Only alphanumeric symbols are allowed");
			}
		} 
		return h;
	}
	
	public static int pow(int base, int exponent) {
		int result = 1;
		for ( int i=0; i<exponent; i++ ) {
			result = (result * base) % MOD;
		}
		return result;
	}
	
	public static List<Integer> search(char[] needle, char[] haystack) {
		List<Integer> results = new ArrayList<>();
		
		if ( needle.length > haystack.length ) {
			return null;
		}
		
		int needleHash = hash(needle, needle.length);
		int rollingHash = hash(haystack, needle.length);
		if ( needleHash == rollingHash ) {
			results.add(0);
		}
		
		int lowOrderRadixPower = pow(RADIX, needle.length-1);
		int maxNeedlePosition = haystack.length-needle.length;
		for ( int i=1; i<=maxNeedlePosition; i++ ) {
			rollingHash = (rollingHash + MOD - (lowOrderRadixPower * haystack[i-1]) % MOD) % MOD;
			rollingHash = (RADIX * rollingHash + haystack[i+needle.length-1]) % MOD;
			
			if ( rollingHash == needleHash ) {
				int matchLen = 0;
				for ( int j=i; j-i<needle.length; j++ ) {
					if ( haystack[j] != needle[j-i] ) {
						break;
					}
					matchLen++;
				}
				if ( matchLen == needle.length ) {
					results.add(i);
					if ( results.size() >= 1000 ) {
						return results;
					}
				}
			}
			
		}
		
		return results;
	}
	
	public static void main(String args[]) throws FileNotFoundException {
		Scanner sc = new Scanner(new FileReader("strmatch.in"));
		String needle = sc.next();
		String haystack = sc.next();
		sc.close();
		
		List<Integer> result = search(needle.toCharArray(), haystack.toCharArray());
		PrintWriter writer = new PrintWriter("strmatch.out");
		if ( result != null ) {
			writer.printf("%d%n",result.size());
			for ( int i : result ) {
				writer.printf("%d ",i);
			}
		} else {
			writer.print(0);
		}
		writer.close();
	}

	
}