Guest User

Untitled

a guest
Oct 30th, 2019
478
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 8.30 KB | None | 0 0
  1. /**
  2.  * Created by Aminul on 10/31/2019.
  3.  */
  4.  
  5. import java.io.*;
  6. import java.util.*;
  7.  
  8. import static java.lang.Math.*;
  9.  
  10. public class Main { // SPOJ_ANARC08C
  11.     public static void main(String[] args) throws Exception {
  12.         FastReader in = new FastReader(System.in);
  13.         PrintWriter pw = new PrintWriter(System.out);
  14.         int testCase = 1;
  15.         LOOP:
  16.         while (true) {
  17.             char[] pat = (in.next() + " ").toCharArray();
  18.             if (pat[0] == 'Q') break;
  19.             pat[pat.length - 1] = 'x';  // adding an extra character for easy implementation //
  20.             Hashing patHash = new Hashing(pat);
  21.             int length_pat = pat.length, idx = 0;
  22.             long pat_hash[] = new long[length_pat]; // hash of each tokens
  23.             int pat_sign[] = new int[length_pat];   // even or odd
  24.             int pat_len[] = new int[length_pat];    // substring length of a token
  25.             int pat_req[] = new int[length_pat];    // minimum number of digits required before this token
  26.  
  27.             for (int i = 0, last = 0, cnt = 0, digitCount = 0, f = -1; i < length_pat; i++) {
  28.                 if (!Character.isDigit(pat[i])) {
  29.                     if (i >= last && (digitCount > 0 || i == length_pat - 1)) {
  30.                         int k = i - 1;
  31.                         if (pat[i] == 'x') k++;
  32.                         pat_hash[idx] = patHash.getHash(last, k);
  33.                         pat_len[idx] = k - last;
  34.                         pat_sign[idx] = f;
  35.                         pat_req[idx++] = cnt;
  36.                         cnt = 0;
  37.                         f = 0;
  38.                         digitCount = 0;
  39.                     }
  40.                     if(f == -1) f = 0;
  41.                     f ^= (pat[i] == '*') ? 0 : 1;  // current sign (even or odd)
  42.                     last = i + 1;
  43.                     cnt += (pat[i] == '*') ? 0 : 1;
  44.                 } else {
  45.                     digitCount++;
  46.                 }
  47.             }
  48.  
  49.             int query = 1;
  50.             while (true) {
  51.                 char[] text = (in.next() + " ").toCharArray();
  52.                 if (text[0] == 'E') break;
  53.                 else if (text[0] == 'Q') break LOOP;
  54.                 text[text.length - 1] = 'x';
  55.                 Hashing textHash = new Hashing(text);
  56.                 int n = text.length;
  57.                 boolean f = true;
  58.                 int j = 0;
  59.                 for (int i = 0, last = 0, sign = -1; i < n; i++) {
  60.                     if (j >= idx) {
  61.                         f = false;
  62.                         break;
  63.                     }
  64.                     int k = i - pat_len[j];
  65.                     if (k < last) continue;
  66.                     else if (k == 0) sign = -1; // neither even, nor odd, query string starts from this position
  67.                     else sign = (k - last) & 1;
  68.                     long currHash = textHash.getHash(k, i);
  69.                     if (currHash == pat_hash[j] &&
  70.                             (sign == pat_sign[j] || (sign == -1 && pat_sign[j] == 0))
  71.                          && (k - last) >= pat_req[j]) {
  72.                         last = i + 1;
  73.                         j++;
  74.                     }
  75.                 }
  76.                 f &= j >= idx;
  77.                 pw.println(testCase + "." + query + ". " + (f ? "match" : "not"));
  78.                 query++;
  79.             }
  80.             testCase++;
  81.         }
  82.  
  83.         pw.close();
  84.     }
  85.  
  86.  
  87.     static void debug(Object... obj) {
  88.         System.err.println(Arrays.deepToString(obj));
  89.     }
  90.  
  91.     static class Hashing {
  92.         long[] hash1, hash2;
  93.         long[] inv1, inv2;
  94.         int n;
  95.  
  96.         long mod1 = 1000000097L;
  97.         long mod2 = (long) 1e9 + 9;
  98.         long multiplier1 = 43, multiplier2 = 31;
  99.         long invMultiplier1 = 441860508;
  100.         long invMultiplier2 = 838709685;
  101.  
  102.         Hashing(char[] s) {
  103.             build_Hash(s);
  104.         }
  105.  
  106.         void build_Hash(char[] s) {
  107.  
  108.             n = s.length;
  109.             hash1 = new long[n + 1];
  110.             hash2 = new long[n + 1];
  111.             inv1 = new long[n + 1];
  112.             inv2 = new long[n + 1];
  113.             inv1[0] = 1;
  114.             inv2[0] = 1;
  115.  
  116.             long p1 = 1;
  117.             long p2 = 1;
  118.             for (int i = 0; i < n; i++) {
  119.                 hash1[i + 1] = (hash1[i] + s[i] * p1) % mod1;
  120.                 p1 = (p1 * multiplier1) % mod1;
  121.                 inv1[i + 1] = inv1[i] * invMultiplier1 % mod1;
  122.                 hash2[i + 1] = (hash2[i] + s[i] * p2) % mod2;
  123.                 p2 = (p2 * multiplier2) % mod2;
  124.                 inv2[i + 1] = inv2[i] * invMultiplier2 % mod2;
  125.             }
  126.         }
  127.  
  128.  
  129.         long getHash(int i, int j) { //0-based
  130.             return getHash_2(i, j - i + 1);
  131.         }
  132.  
  133.         long getHash_2(int i, int len) { //i is 0  based indexed
  134.             return (((hash1[i + len] - hash1[i] + mod1) * inv1[i] % mod1) << 32)
  135.                     + (hash2[i + len] - hash2[i] + mod2) * inv2[i] % mod2;
  136.         }
  137.  
  138.         long revHash(int i, int j) { ////0-based
  139.             return getHash(n - j - 1, n - i - 1);
  140.         }
  141.     }
  142.  
  143.     static class FastReader {
  144.         InputStream is;
  145.         private byte[] inbuf = new byte[1024];
  146.         private int lenbuf = 0, ptrbuf = 0;
  147.  
  148.         public FastReader(InputStream is) {
  149.             this.is = is;
  150.         }
  151.  
  152.         public int readByte() {
  153.             if (lenbuf == -1) throw new InputMismatchException();
  154.             if (ptrbuf >= lenbuf) {
  155.                 ptrbuf = 0;
  156.                 try {
  157.                     lenbuf = is.read(inbuf);
  158.                 } catch (IOException e) {
  159.                     throw new InputMismatchException();
  160.                 }
  161.                 if (lenbuf <= 0) return -1;
  162.             }
  163.             return inbuf[ptrbuf++];
  164.         }
  165.  
  166.         public boolean isSpaceChar(int c) {
  167.             return !(c >= 33 && c <= 126);
  168.         }
  169.  
  170.         private boolean isEndOfLine(int c) {
  171.             return c == '\n' || c == '\r' || c == -1;
  172.         }
  173.  
  174.         public int skip() {
  175.             int b;
  176.             while ((b = readByte()) != -1 && isSpaceChar(b)) ;
  177.             return b;
  178.         }
  179.  
  180.         public String next() {
  181.             int b = skip();
  182.             StringBuilder sb = new StringBuilder();
  183.             while (!(isSpaceChar(b))) {
  184.                 sb.appendCodePoint(b);
  185.                 b = readByte();
  186.             }
  187.             return sb.toString();
  188.         }
  189.  
  190.  
  191.         public String nextLine() {
  192.             int c = skip();
  193.             StringBuilder sb = new StringBuilder();
  194.             while (!isEndOfLine(c)) {
  195.                 sb.appendCodePoint(c);
  196.                 c = readByte();
  197.             }
  198.             return sb.toString();
  199.         }
  200.  
  201.         public int nextInt() {
  202.             int num = 0, b;
  203.             boolean minus = false;
  204.             while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
  205.             if (b == '-') {
  206.                 minus = true;
  207.                 b = readByte();
  208.             }
  209.             while (true) {
  210.                 if (b >= '0' && b <= '9') {
  211.                     num = (num << 3) + (num << 1) + (b - '0');
  212.                 } else {
  213.                     return minus ? -num : num;
  214.                 }
  215.                 b = readByte();
  216.             }
  217.         }
  218.  
  219.         public long nextLong() {
  220.             long num = 0;
  221.             int b;
  222.             boolean minus = false;
  223.             while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
  224.             if (b == '-') {
  225.                 minus = true;
  226.                 b = readByte();
  227.             }
  228.  
  229.             while (true) {
  230.                 if (b >= '0' && b <= '9') {
  231.                     num = (num << 3) + (num << 1) + (b - '0');
  232.                 } else {
  233.                     return minus ? -num : num;
  234.                 }
  235.                 b = readByte();
  236.             }
  237.         }
  238.  
  239.         public double nextDouble() {
  240.             return Double.parseDouble(next());
  241.         }
  242.  
  243.         public char[] next(int n) {
  244.             char[] buf = new char[n];
  245.             int b = skip(), p = 0;
  246.             while (p < n && !(isSpaceChar(b))) {
  247.                 buf[p++] = (char) b;
  248.                 b = readByte();
  249.             }
  250.             return n == p ? buf : Arrays.copyOf(buf, p);
  251.         }
  252.  
  253.         public char readChar() {
  254.             return (char) skip();
  255.         }
  256.     }
  257. }
Advertisement
Add Comment
Please, Sign In to add comment