Advertisement
Guest User

Untitled

a guest
Mar 23rd, 2015
463
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.25 KB | None | 0 0
  1. /*
  2. ID: david.y1
  3. PROB: censor
  4. LANG: JAVA
  5. */
  6. import java.io.*;
  7. import java.util.*;
  8.  
  9. public class censor {
  10. public static void main(String[] args) throws IOException {
  11. BufferedReader f = new BufferedReader(new FileReader("censor.in"));
  12. //StringTokenizer st = new StringTokenizer(f.readLine());
  13. System.setOut(new PrintStream(new File("censor.out")));
  14. String t = f.readLine();
  15. String p = f.readLine();
  16. Node n = kmpsearch(t,p);
  17. String s = "";
  18. boolean root = true;
  19. while(true){
  20. if(n == null){
  21. break;
  22. }
  23. if(root){
  24. n = n.child;
  25. root = false;
  26. }
  27. else{
  28. s += n.c;
  29. n = n.child;
  30. }
  31.  
  32.  
  33. }
  34. System.out.println(s);
  35. }
  36. public static class Node{
  37. public Node(char ch){
  38. c = ch;
  39. }
  40. char c;
  41. Node parent;
  42. Node child;
  43. int k;
  44. }
  45. public static Node print(String t, String p){
  46. Node root = new Node('z');
  47. Node temp = root;
  48. for(int i = 0;i<t.length();i++){
  49. temp.child = new Node(t.charAt(i));
  50. temp = temp.child;
  51. }
  52. return root;
  53. }
  54. public static Node kmpsearch(String t, String p){
  55. HashMap<Integer,Node> map = new HashMap<Integer,Node>();
  56. Node root = new Node('z');
  57. Node temp = root;
  58. int[] prefixofsuffix = generatefunction(p);
  59. int k = -1;
  60. int ii = 0;
  61. map.put(-1, root);
  62. for(int i = 0;i<t.length();i++){
  63. //System.out.println(t.charAt(i));
  64. temp.child = new Node(t.charAt(i));
  65. temp.child.parent = temp;
  66. temp = temp.child;
  67. map.put(ii,temp);
  68. while(k > -1 && p.charAt(k+1)!=t.charAt(i)){
  69. k = prefixofsuffix[k];
  70. }
  71. if(p.charAt(k+1)==t.charAt(i)){
  72. k++;
  73. }
  74. temp.k = k;
  75. if(k==p.length()-1){
  76. //System.out.println(ii);
  77. temp = map.get(ii-p.length());
  78. //map.get(-69);
  79. //System.out.println(temp.c);
  80. temp.child = null;
  81. k = temp.k;
  82. ii -= p.length();
  83. //System.out.println(ii);
  84. }
  85. ii++;
  86. }
  87. return root;
  88. }
  89. public static int[] generatefunction(String p){
  90. int[] prefixofsuffix = new int[p.length()];
  91. int k = -1;
  92. prefixofsuffix[0] = -1;
  93. for(int i = 1;i<p.length();i++){
  94. while(k>-1 && p.charAt(k+1)!=p.charAt(i)){
  95. k = prefixofsuffix[k];
  96. }
  97. if(p.charAt(k+1)==p.charAt(i)){
  98. k++;
  99. }
  100. prefixofsuffix[i] = k;
  101. }
  102. return prefixofsuffix;
  103. }
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement