fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty
stderr
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)