#121581 (Java) No.430 文字列検索

• 問題: No.430 文字列検索
• ユーザー: yuppe19 😺
• 提出日時: 2016-10-04 19:19:18
• 言語: Java (openjdk 23)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 7,684 bytes
• コンパイル時間: 1,607 ms
• コンパイル使用メモリ: 80,440 KB
• 最終ジャッジ日時: 2024-11-10 00:09:02
• 合計ジャッジ時間: 1,917 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

コンパイルメッセージ

Main.java:82: warning: [strictfp] as of release 17, all floating-point expressions are evaluated strictly and 'strictfp' is not required
strictfp class MersenneTwister extends Random { // {{{ MersenneTwister
         ^
1 error
1 warning

ソースコード

import java.io.*;
import java.util.*;

import static java.lang.Math.*;

class FastScanner { // {{{
  private final InputStream in = System.in;
  private final byte[] buffer = new byte[1024];
  private int ptr = 0;
  private int buflen = 0;
  private boolean hasNextByte() {
    if(ptr < buflen) { return true; }
    ptr = 0;
    try {
      buflen = in.read(buffer);
    } catch(IOException ex) {
      ex.printStackTrace();
    }
    if(buflen <= 0) { return false; }
    return true;
  }
  private int readByte() { if(hasNextByte()) { return buffer[ptr++]; } return -1; }
  private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; }
  private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) { ptr++; } }
  public boolean hasNext() { skipUnprintable(); return hasNextByte(); }
  public String next() {
    if(!hasNext()) { throw new NoSuchElementException(); }
    StringBuilder sb = new StringBuilder();
    int b = readByte();
    while(isPrintableChar(b)) {
      sb.appendCodePoint(b);
      b = readByte();
    }
    return sb.toString();
  }
  public long nextLong() {
    if(!hasNext()) { throw new NoSuchElementException(); }
    long n = 0;
    boolean minus = false;
    int b = readByte();
    if(b == '-') {
      minus = true;
      b = readByte();
    }
    if(b < '0' || '9' < b) { throw new NumberFormatException(); }
    while(true) {
      if('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if(b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
      b = readByte();
    }
  }
  public int nextInt() {
    if(!hasNext()) { throw new NoSuchElementException(); }
    int n = 0;
    boolean minus = false;
    int b = readByte();
    if(b == '-') {
      minus = true;
      b = readByte();
    }
    if(b < '0' || '9' < b) { throw new NumberFormatException(); }
    while(true) {
      if('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if(b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
      b = readByte();
    }
  }
} // }}}

strictfp class MersenneTwister extends Random { // {{{ MersenneTwister
  private static final long serialVersionUID = -515082678588212038L;
	private final static int UPPER_MASK = 0x80000000;
	private final static int LOWER_MASK = 0x7fffffff;

	private final static int N = 624;
	private final static int M = 397;
	private final static int[] MAGIC = { 0x0, 0x9908b0df };

  private transient int[] mt;
  private transient int mti;

  public MersenneTwister() {
    super(0L);
    setSeed(System.currentTimeMillis());
  }

  public MersenneTwister(long seed) {
    super(seed);
    this.setSeed(seed);
  }

  public MersenneTwister(int[] buf) {
    super(0L);
    setSeed(buf);
  }

  private final void setSeed(int seed) {
    if(mt == null) { mt = new int[N]; }
    mt[0] = seed;
    for(mti=1; mti<N; ++mti) {
      mt[mti] = (1812433253 * (mt[mti-1] ^ (mt[mti-1] >>> 30)) + mti);
    }
  }

  public final synchronized void setSeed(long seed) {
    setSeed((int)seed);
  }

  public final synchronized void setSeed(int[] buf) {
    int length = buf.length;
    if(length == 0) { throw new IllegalArgumentException("buf is empty"); }
    int i = 1, j = 0, k = (N > length ? N : length);
    setSeed(19971007);
    for( ; k>0; --k) {
      mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >>> 30)) * 1664525)) + buf[j] + j;
      ++i; ++j;
      if(i >= N) { mt[0] = mt[N-1]; i = 1; }
      if(j >= length) { j = 0; }
    }
    for(k=N-1; k>0; --k) {
      mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >>> 30)) * 1566083941)) - i;
      ++i;
      if(i >= N) { mt[0] = mt[N-1]; i = 1; }
    }
    mt[0] = UPPER_MASK;
  }

  protected final synchronized int next(int bits) {
    int y, kk;
    if(mti >= N) {
      for(kk=0; kk<N-M; ++kk) {
        y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
        mt[kk] = mt[kk+M] ^ (y >>> 1) ^ MAGIC[y & 0x1];
      }
      for( ; kk<N-1; ++kk) {
        y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
        mt[kk] = mt[kk+(M-N)] ^ (y >>> 1) ^ MAGIC[y & 0x1];
      }
      y = (mt[N-1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
      mt[N-1] = mt[M-1] ^ (y >>> 1) ^ MAGIC[y & 0x1];
      mti = 0;
    }
    y = mt[mti++];
    y ^= (y >>> 11);
    y ^= (y << 7) & 0x9d2c5680;
    y ^= (y << 15) & 0xefc60000;
    y ^= (y >>> 18);
    return (y >>> (32 - bits));
  }

  public int nextInt31() { return nextInt() >>> 1; }
  public long nextLong63() { return nextLong() >>> 1; }

  public <T> void shuffle(List<T> list) {
    int n = list.size();
    for(int i=n-1; i>=1; --i) {
      int k = nextInt31() % (i + 1);
      if(k == i) { continue; }
      Collections.swap(list, k, i);
    }
  }
} // }}}

class MyUtil {
  private MyUtil() {}
  public static List<Long> segmentSieve(long a, long b) {
    int sqb = (int)sqrt(b);
    boolean[] isPrimeSmall = new boolean[sqb+1];
    Arrays.fill(isPrimeSmall, true);
    isPrimeSmall[0] = isPrimeSmall[1] = true;
    boolean[] isPrime = new boolean[(int)(b-a)];
    Arrays.fill(isPrime, true);
    isPrime[0] = a != 1;
    for(long i=2; i*i<b; ++i) {
      if(isPrimeSmall[(int)i]) {
        for(long j=2*i; j*j<b; j+=i) { isPrimeSmall[(int)j] = false; }
        for(long j=max(2, ((a+i-1)/i))*i; j<b; j+=i) { isPrime[(int)(j-a)] = false; }
      }
    }
    List<Long> res = new ArrayList<>();
    for(long i=0; i<b-a; ++i) {
      if(isPrime[(int)i]) { res.add(i+a); }
    }
    return res;
  }
}

class RollingHash {
  private String s;
  private long[][] b, H;
  private long[] mods, bases;

  RollingHash(String s, long[] mods, long[] bases) {
    this.s = s;
    this.mods = mods;
    this.bases = bases;
    b = new long[2][0];
    H = new long[2][0];
    int n = s.length();
    for(int j=0; j<2; ++j) {
      long B = bases[j] % mods[j];
      b[j] = new long[n+1];
      H[j] = new long[n+1];
      b[j][0] = 1;
      H[j][0] = 0;
      for(int i=0; i<n; ++i) {
        b[j][i+1] = b[j][i] * B;
        b[j][i+1] %= mods[j];
        H[j][i+1] = H[j][i] * B + (int)s.charAt(i);
        H[j][i+1] %= mods[j];
      }
    }
  }

  long calcHash(int l, int r) {
    long h0 = (H[0][r] - b[0][r-l+1] * H[0][l-1]) % mods[0];
    if(h0 < 0) { h0 += mods[0]; }
    long h1 = (H[1][r] - b[1][r-l+1] * H[1][l-1]) % mods[1];
    if(h1 < 0) { h1 += mods[1]; }
    long hash = (h0 << 31) + h1;
    return hash;
  }
}

public class Main0430 {
  private void solve() {
    MersenneTwister mersenne = new MersenneTwister();
    long LO = (long)pow(2L, 30),
         HI = LO + 100000;
    List<Long> primes = MyUtil.segmentSieve(LO, HI);
    mersenne.shuffle(primes);
    long[] mods = new long[] {primes.get(0), primes.get(1)},
           bases = new long[] {mersenne.nextLong63(), mersenne.nextLong63()};
    
    FastScanner sc = new FastScanner();
    String s = sc.next();
    RollingHash rhs = new RollingHash(s, mods, bases);
    int n = s.length();
    
    long[][] cache = new long[11][n];
    for(int len=1; len<=10; ++len) {
      for(int start=0; start+len<=n; ++start) {
        cache[len][start] = rhs.calcHash(start+1, start+len);
      }
    }

    int M = sc.nextInt();
    int res = 0;
    for(int i=0; i<M; ++i) {
      String t = sc.next();
      int m = t.length();
      RollingHash rht = new RollingHash(t, mods, bases);
      long hasht = rht.calcHash(1, m);
      for(int start=0; start<n; ++start) {
        if(cache[m][start] == hasht) { ++res; }
      }
    }
    System.out.println(res);
  }

  public static void main(String[] args) {
    new Main0430().solve();
  }
}