Pagini recente » Cod sursa (job #1863384) | Cod sursa (job #472486) | Cod sursa (job #2366832) | Cod sursa (job #2403431) | Cod sursa (job #1420258)
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();
}
}