Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- import java.io.IOException;
- public class SDA1819T4 {
- /**
- * main adalah fungsi utama untuk input dan memanggil instruksi yang
- * sesuai dengan input instruksinya
- *
- * @param args Unused.
- * @return Nothing.
- */
- public static void main(String args[]) throws IOException {
- BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
- String kata = reader.readLine();
- int jml = Integer.parseInt(reader.readLine());
- for (int i = 0; i < jml; i++) {
- String inp[] = reader.readLine().split(" ");
- if (inp[0].equals("0")) {
- System.out.println(query0(kata, inp[1]));
- } else if (inp[0].equals("1")) {
- }
- }
- }
- public static int query0(String inp, String str) {
- int pjgInp = inp.length();
- int pjgStr = str.length();
- if (pjgStr > pjgInp) {
- return 0;
- }
- String sub = inp.substring(0, pjgStr);
- int subHash1 = HashTable.hash1(sub);
- int subHash2 = HashTable.hash2(sub);
- int strHash1 = HashTable.hash1(str);
- int strHash2 = HashTable.hash2(str);
- int val = 0;
- for (int i = 0; i <= pjgInp - pjgStr; i++) {
- if (subHash1 == strHash1 && subHash2 == strHash2) {
- val++;
- }
- if (i + pjgStr > pjgInp - 1) {
- break;
- }
- char firstChar = inp.charAt(i);
- char lastChar = inp.charAt(i + pjgStr);
- int firstVal1 = (int) firstChar * (int) Math.pow(HashTable.BASE1, pjgStr - 1);
- int firstVal2 = (int) firstChar * (int) Math.pow(HashTable.BASE2, pjgStr - 1);
- int lastVal = (int) lastChar;
- subHash1 = (subHash1 - firstVal1) * HashTable.BASE1 + lastVal;
- subHash2 = (subHash2 - firstVal2) * HashTable.BASE2 + lastVal;
- }
- return val;
- }
- // public static int query1(String inp) {
- // int pjgInp = inp.length();
- // int pjgStr, subHash1, subHash2;
- // String str;
- // String val = 0;
- // String subMax;
- // for (int i = 1; i < pjgInp; i++) {
- // str = inp.substring(0, i);
- // subHash1 = HashTable.hash1(str);
- // subHash2 = HashTable.hash2(str);
- // for (int j = 0; j <= pjgInp - i; j++) {
- // if (HashTable.exist(subHash1, subHash2)) {
- // HashTable.arr[subHash1] =
- // } else {
- // }
- // }
- // }
- // }
- }
- class Substring {
- public int hash2;
- public Substring coll = null;
- public int freq = 0;
- public Substring(int hash2) {
- this.hash2 = hash2;
- }
- }
- class HashTable {
- public static final int BASE1 = 31;
- public static final int BASE2 = 29;
- public static Substring[] arr = new Substring[98317];
- public static int hash1(String str) {
- int pjg = str.length();
- int val = 0;
- int sub;
- for (int i = 0; i < pjg; i++) {
- sub = (int) str.charAt(i);
- val += sub * (Math.pow(BASE1, pjg - i - 1));
- }
- return val;
- }
- public static int hash2(String str) {
- int pjg = str.length();
- int val = 0;
- int sub;
- for (int i = 0; i < pjg; i++) {
- sub = (int) str.charAt(i);
- val += sub * (Math.pow(BASE2, pjg - i - 1));
- }
- return val;
- }
- public static boolean exist(int hash1, int hash2) {
- if (arr[hash1] == null) {
- return false;
- } else if (arr[hash1].hash2 == hash2) {
- return true;
- } else if (arr[hash1].coll == null) {
- return false;
- } else {
- Substring sub = arr[hash1].coll;
- if (sub.hash2 == hash2) {
- return true;
- }
- while (sub.coll != null) {
- sub = sub.coll;
- if (sub.hash2 == hash2) {
- return true;
- }
- }
- return false;
- }
- }
- // public static void save(int hash1, int hash2) {
- // }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement