fork(1) download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. import java.math.BigInteger;
  4. import java.util.Map.Entry;
  5.  
  6. import static java.lang.Math.*;
  7.  
  8. public class Main extends PrintWriter {
  9.  
  10.     void run() {
  11.  
  12.         String s = next();
  13.         Map<String, List<Integer>> f = new HashMap<String, List<Integer>>(1 << 21);
  14.         int n = s.length();
  15.  
  16.         int m = nextInt();
  17.  
  18.         int[] l = new int[m];
  19.         int[] r = new int[m];
  20.  
  21.         String[] p = new String[m];
  22.  
  23.         for (int j = 0; j < m; j++) {
  24.             l[j] = nextInt() - 1;
  25.             r[j] = nextInt() - 0;
  26.  
  27.             String str = p[j] = next();
  28.             int k = str.length();
  29.  
  30.             int li = 0;
  31.  
  32.             while (li < k) {
  33.                 while (li < k && str.charAt(li) == '*') {
  34.                     ++li;
  35.                 }
  36.                 int ri = li;
  37.  
  38.                 while (ri < k && str.charAt(ri) != '*') {
  39.                     ++ri;
  40.                 }
  41.  
  42.                 if (li < ri) {
  43.                     String sub = str.substring(li, ri);
  44.                     f.put(sub, new ArrayList<Integer>());
  45.                 }
  46.                 li = ri;
  47.             }
  48.         }
  49.  
  50.         for (int i = 0; i < n; i++) {
  51.             for (int len = min(10, n - i); len >= 1; len--) {
  52.                 List<Integer> list = f.get(s.substring(i, i + len));
  53.                 if (list != null) {
  54.                     list.add(i);
  55.                 }
  56.             }
  57.         }
  58.  
  59.         for (int j = 0; j < m; j++) {
  60.             boolean ok = true;
  61.             int i = l[j];
  62.  
  63.             String str = p[j];
  64.             int k = str.length();
  65.  
  66.             int li = 0;
  67.  
  68.             while (ok && li < k) {
  69.                 while (li < k && str.charAt(li) == '*') {
  70.                     ++li;
  71.                 }
  72.                 int ri = li;
  73.  
  74.                 while (ri < k && str.charAt(ri) != '*') {
  75.                     ++ri;
  76.                 }
  77.  
  78.                 if (li < ri) {
  79.                     String sub = str.substring(li, ri);
  80.                     List<Integer> list = f.get(sub);
  81.  
  82.                     if (list.isEmpty()) {
  83.                         ok = false;
  84.                         break;
  85.                     }
  86.  
  87.                     int index = Collections.binarySearch(list, i);
  88.  
  89.                     if (index < 0) {
  90.                         index = ~index;
  91.                     }
  92.  
  93.                     if (index >= list.size()) {
  94.                         ok = false;
  95.                         break;
  96.                     }
  97.  
  98.                     i = list.get(index);
  99.  
  100.                     if (li == 0) {
  101.                         ok &= i == l[j];
  102.                     }
  103.  
  104.                     i += sub.length();
  105.  
  106.                     if (ri == k) {
  107.                         ok &= i == r[j];
  108.                     }
  109.  
  110.                     ok &= i <= r[j];
  111.                 }
  112.                 li = ri;
  113.             }
  114.  
  115.             println(ok ? "Yes" : "No");
  116.         }
  117.  
  118.     }
  119.  
  120.     public static boolean nextPermutation(int[] permutation) {
  121.         int n = permutation.length, a = n - 2;
  122.         while (0 <= a && permutation[a] >= permutation[a + 1]) {
  123.             a--;
  124.         }
  125.         if (a == -1) {
  126.             return false;
  127.         }
  128.  
  129.         int b = n - 1;
  130.         while (permutation[b] <= permutation[a]) {
  131.             b--;
  132.         }
  133.  
  134.         swap(permutation, a, b);
  135.         for (int i = a + 1, j = n - 1; i < j; i++, j--) {
  136.             swap(permutation, i, j);
  137.         }
  138.         return true;
  139.     }
  140.  
  141.     public static void swap(int[] array, int i, int j) {
  142.         if (i == j) {
  143.             return;
  144.         }
  145.         array[i] ^= array[j];
  146.         array[j] ^= array[i];
  147.         array[i] ^= array[j];
  148.     }
  149.  
  150.     int[][] nextMatrix(int n, int m) {
  151.         int[][] matrix = new int[n][m];
  152.         for (int i = 0; i < n; i++)
  153.             for (int j = 0; j < m; j++)
  154.                 matrix[i][j] = nextInt();
  155.         return matrix;
  156.     }
  157.  
  158.     String next() {
  159.         while (!tokenizer.hasMoreTokens())
  160.             tokenizer = new StringTokenizer(nextLine());
  161.         return tokenizer.nextToken();
  162.     }
  163.  
  164.     boolean hasNext() {
  165.         while (!tokenizer.hasMoreTokens()) {
  166.             String line = nextLine();
  167.             if (line == null) {
  168.                 return false;
  169.             }
  170.             tokenizer = new StringTokenizer(line);
  171.         }
  172.         return true;
  173.     }
  174.  
  175.     int[] nextArray(int n) {
  176.         int[] array = new int[n];
  177.         for (int i = 0; i < n; i++) {
  178.             array[i] = nextInt();
  179.         }
  180.         return array;
  181.     }
  182.  
  183.     int nextInt() {
  184.         return Integer.parseInt(next());
  185.     }
  186.  
  187.     long nextLong() {
  188.         return Long.parseLong(next());
  189.     }
  190.  
  191.     double nextDouble() {
  192.         return Double.parseDouble(next());
  193.     }
  194.  
  195.     String nextLine() {
  196.         try {
  197.             return reader.readLine();
  198.         } catch (IOException err) {
  199.             return null;
  200.         }
  201.     }
  202.  
  203.     public Main(OutputStream outputStream) {
  204.         super(outputStream);
  205.     }
  206.  
  207.     static BufferedReader reader;
  208.     static StringTokenizer tokenizer = new StringTokenizer("");
  209.     static Random rnd = new Random();
  210.  
  211.     public static void main(String[] args) throws IOException {
  212.         reader = new BufferedReader(new InputStreamReader(System.in));
  213.         Main Main = new Main(System.out);
  214.  
  215.         Main.run();
  216.         Main.close();
  217.         reader.close();
  218.     }
  219. }
Success #stdin #stdout 0.06s 2841600KB
comments (?)
stdin
copy 
bbccbcaccb
1
1 6 bb*
stdout
copy 
Yes
https://ideone.com/M3yxtj
bbccbcaccb
1
1 6 bb*
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!