fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     public static void main(String args[]) {
  5.         Scanner sc = new Scanner(System.in);
  6.         int n = sc.nextInt();
  7.         while (n-- > 0) {
  8.             String str = "abacaba";
  9.             int count = 0;
  10.             int x = sc.nextInt();
  11.             String s = sc.next();
  12.             StringBuilder sb = new StringBuilder(s);
  13.             int j = 0;
  14.             count = rabin_karp(str, s).size();
  15.             //more than 1
  16.             if (count > 1) {
  17.                 System.out.println("No");
  18.             //no str in s
  19.             } else if (count == 0) {
  20.                 int i;
  21.                 for (i = 0; i < x; i++) {
  22.                     while (j < str.length() && i < s.length() && (str.charAt(j) == s.charAt(i) || s.charAt(i) == '?')) {
  23.                         if (s.charAt(i) == '?')
  24.                             sb.setCharAt(i, str.charAt(j));
  25.                         i++;
  26.                         j++;
  27.                     }
  28.                     if (j >= str.length()) {
  29.                         count++;
  30.                         break;
  31.                     }
  32.                     j = 0;
  33.                 }
  34.                 for (; i < sb.length();i++) {
  35.                     if (sb.charAt(i) == '?')
  36.                         sb.setCharAt(i, 'd');
  37.                 }
  38.                 if(count==1) {
  39.                     System.out.println("Yes");
  40.                     System.out.println(sb.toString());
  41.                 }
  42.                 else
  43.                     System.out.println("NO");
  44.             } else {
  45.                 for (int i = 0; i < s.length(); i++) {
  46.                     if (s.charAt(i) == '?')
  47.                         sb.setCharAt(i, 'd');
  48.                 }
  49.                 System.out.println("Yes");
  50.                 System.out.println(sb.toString());
  51.             }
  52.         }
  53.     }
  54.     //find substring occurrence
  55.     static List<Long> rabin_karp(String s, String t) {
  56.         int p = 31;
  57.         int m = (int) 1e9 + 9;
  58.         long S = s.length(), T = t.length();
  59.  
  60.         Map<Long, Long> p_pow = new HashMap<>();
  61.         p_pow.put(0L, 1L);
  62.         for (long i = 1; i < Math.max(S, T); i++)
  63.             p_pow.put(i, (p_pow.get(i - 1) * p) % m);
  64.  
  65.         Map<Long, Long> h = new HashMap<>();
  66.         for (long i = 0; i < T + 2; i++)
  67.             h.put(i, 0L);
  68.         for (long i = 0; i < T; i++)
  69.             h.put(i + 1, (h.get(i) + (t.charAt((int) i) - 'a' + 1) * p_pow.get(i)) % m);
  70.         long h_s = 0;
  71.         for (long i = 0; i < S; i++)
  72.             h_s = (h_s + (s.charAt((int) i) - 'a' + 1) * p_pow.get(i)) % m;
  73.  
  74.         List<Long> occurences = new ArrayList<>();
  75.         for (long i = 0; i + S - 1 < T; i++) {
  76.             long cur_h = (h.get(i + S) + m - h.get(i)) % m;
  77.             if (cur_h == h_s * p_pow.get(i) % m)
  78.                 occurences.add(i);
  79.         }
  80.         return occurences;
  81.     }
  82. }
Runtime error #stdin #stdout #stderr 0.14s 35556KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.util.NoSuchElementException
	at java.base/java.util.Scanner.throwFor(Scanner.java:937)
	at java.base/java.util.Scanner.next(Scanner.java:1594)
	at java.base/java.util.Scanner.nextInt(Scanner.java:2258)
	at java.base/java.util.Scanner.nextInt(Scanner.java:2212)
	at Main.main(Main.java:6)
https://ideone.com/rajqqD
language:
Java (HotSpot 12)
created:
3 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!