Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Created by Aminul on 10/31/2019.
- */
- import java.io.*;
- import java.util.*;
- import static java.lang.Math.*;
- public class Main { // SPOJ_ANARC08C
- public static void main(String[] args) throws Exception {
- FastReader in = new FastReader(System.in);
- PrintWriter pw = new PrintWriter(System.out);
- int testCase = 1;
- LOOP:
- while (true) {
- char[] pat = (in.next() + " ").toCharArray();
- if (pat[0] == 'Q') break;
- pat[pat.length - 1] = 'x'; // adding an extra character for easy implementation //
- Hashing patHash = new Hashing(pat);
- int length_pat = pat.length, idx = 0;
- long pat_hash[] = new long[length_pat]; // hash of each tokens
- int pat_sign[] = new int[length_pat]; // even or odd
- int pat_len[] = new int[length_pat]; // substring length of a token
- int pat_req[] = new int[length_pat]; // minimum number of digits required before this token
- for (int i = 0, last = 0, cnt = 0, digitCount = 0, f = -1; i < length_pat; i++) {
- if (!Character.isDigit(pat[i])) {
- if (i >= last && (digitCount > 0 || i == length_pat - 1)) {
- int k = i - 1;
- if (pat[i] == 'x') k++;
- pat_hash[idx] = patHash.getHash(last, k);
- pat_len[idx] = k - last;
- pat_sign[idx] = f;
- pat_req[idx++] = cnt;
- cnt = 0;
- f = 0;
- digitCount = 0;
- }
- if(f == -1) f = 0;
- f ^= (pat[i] == '*') ? 0 : 1; // current sign (even or odd)
- last = i + 1;
- cnt += (pat[i] == '*') ? 0 : 1;
- } else {
- digitCount++;
- }
- }
- int query = 1;
- while (true) {
- char[] text = (in.next() + " ").toCharArray();
- if (text[0] == 'E') break;
- else if (text[0] == 'Q') break LOOP;
- text[text.length - 1] = 'x';
- Hashing textHash = new Hashing(text);
- int n = text.length;
- boolean f = true;
- int j = 0;
- for (int i = 0, last = 0, sign = -1; i < n; i++) {
- if (j >= idx) {
- f = false;
- break;
- }
- int k = i - pat_len[j];
- if (k < last) continue;
- else if (k == 0) sign = -1; // neither even, nor odd, query string starts from this position
- else sign = (k - last) & 1;
- long currHash = textHash.getHash(k, i);
- if (currHash == pat_hash[j] &&
- (sign == pat_sign[j] || (sign == -1 && pat_sign[j] == 0))
- && (k - last) >= pat_req[j]) {
- last = i + 1;
- j++;
- }
- }
- f &= j >= idx;
- pw.println(testCase + "." + query + ". " + (f ? "match" : "not"));
- query++;
- }
- testCase++;
- }
- pw.close();
- }
- static void debug(Object... obj) {
- System.err.println(Arrays.deepToString(obj));
- }
- static class Hashing {
- long[] hash1, hash2;
- long[] inv1, inv2;
- int n;
- long mod1 = 1000000097L;
- long mod2 = (long) 1e9 + 9;
- long multiplier1 = 43, multiplier2 = 31;
- long invMultiplier1 = 441860508;
- long invMultiplier2 = 838709685;
- Hashing(char[] s) {
- build_Hash(s);
- }
- void build_Hash(char[] s) {
- n = s.length;
- hash1 = new long[n + 1];
- hash2 = new long[n + 1];
- inv1 = new long[n + 1];
- inv2 = new long[n + 1];
- inv1[0] = 1;
- inv2[0] = 1;
- long p1 = 1;
- long p2 = 1;
- for (int i = 0; i < n; i++) {
- hash1[i + 1] = (hash1[i] + s[i] * p1) % mod1;
- p1 = (p1 * multiplier1) % mod1;
- inv1[i + 1] = inv1[i] * invMultiplier1 % mod1;
- hash2[i + 1] = (hash2[i] + s[i] * p2) % mod2;
- p2 = (p2 * multiplier2) % mod2;
- inv2[i + 1] = inv2[i] * invMultiplier2 % mod2;
- }
- }
- long getHash(int i, int j) { //0-based
- return getHash_2(i, j - i + 1);
- }
- long getHash_2(int i, int len) { //i is 0 based indexed
- return (((hash1[i + len] - hash1[i] + mod1) * inv1[i] % mod1) << 32)
- + (hash2[i + len] - hash2[i] + mod2) * inv2[i] % mod2;
- }
- long revHash(int i, int j) { ////0-based
- return getHash(n - j - 1, n - i - 1);
- }
- }
- static class FastReader {
- InputStream is;
- private byte[] inbuf = new byte[1024];
- private int lenbuf = 0, ptrbuf = 0;
- public FastReader(InputStream is) {
- this.is = is;
- }
- public int readByte() {
- if (lenbuf == -1) throw new InputMismatchException();
- if (ptrbuf >= lenbuf) {
- ptrbuf = 0;
- try {
- lenbuf = is.read(inbuf);
- } catch (IOException e) {
- throw new InputMismatchException();
- }
- if (lenbuf <= 0) return -1;
- }
- return inbuf[ptrbuf++];
- }
- public boolean isSpaceChar(int c) {
- return !(c >= 33 && c <= 126);
- }
- private boolean isEndOfLine(int c) {
- return c == '\n' || c == '\r' || c == -1;
- }
- public int skip() {
- int b;
- while ((b = readByte()) != -1 && isSpaceChar(b)) ;
- return b;
- }
- public String next() {
- int b = skip();
- StringBuilder sb = new StringBuilder();
- while (!(isSpaceChar(b))) {
- sb.appendCodePoint(b);
- b = readByte();
- }
- return sb.toString();
- }
- public String nextLine() {
- int c = skip();
- StringBuilder sb = new StringBuilder();
- while (!isEndOfLine(c)) {
- sb.appendCodePoint(c);
- c = readByte();
- }
- return sb.toString();
- }
- public int nextInt() {
- int num = 0, b;
- boolean minus = false;
- while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
- if (b == '-') {
- minus = true;
- b = readByte();
- }
- while (true) {
- if (b >= '0' && b <= '9') {
- num = (num << 3) + (num << 1) + (b - '0');
- } else {
- return minus ? -num : num;
- }
- b = readByte();
- }
- }
- public long nextLong() {
- long num = 0;
- int b;
- boolean minus = false;
- while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
- if (b == '-') {
- minus = true;
- b = readByte();
- }
- while (true) {
- if (b >= '0' && b <= '9') {
- num = (num << 3) + (num << 1) + (b - '0');
- } else {
- return minus ? -num : num;
- }
- b = readByte();
- }
- }
- public double nextDouble() {
- return Double.parseDouble(next());
- }
- public char[] next(int n) {
- char[] buf = new char[n];
- int b = skip(), p = 0;
- while (p < n && !(isSpaceChar(b))) {
- buf[p++] = (char) b;
- b = readByte();
- }
- return n == p ? buf : Arrays.copyOf(buf, p);
- }
- public char readChar() {
- return (char) skip();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment