Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ID: david.y1
- PROB: censor
- LANG: JAVA
- */
- import java.io.*;
- import java.util.*;
- public class censor {
- public static void main(String[] args) throws IOException {
- BufferedReader f = new BufferedReader(new FileReader("censor.in"));
- //StringTokenizer st = new StringTokenizer(f.readLine());
- System.setOut(new PrintStream(new File("censor.out")));
- String t = f.readLine();
- String p = f.readLine();
- Node n = kmpsearch(t,p);
- String s = "";
- boolean root = true;
- while(true){
- if(n == null){
- break;
- }
- if(root){
- n = n.child;
- root = false;
- }
- else{
- s += n.c;
- n = n.child;
- }
- }
- System.out.println(s);
- }
- public static class Node{
- public Node(char ch){
- c = ch;
- }
- char c;
- Node parent;
- Node child;
- int k;
- }
- public static Node print(String t, String p){
- Node root = new Node('z');
- Node temp = root;
- for(int i = 0;i<t.length();i++){
- temp.child = new Node(t.charAt(i));
- temp = temp.child;
- }
- return root;
- }
- public static Node kmpsearch(String t, String p){
- HashMap<Integer,Node> map = new HashMap<Integer,Node>();
- Node root = new Node('z');
- Node temp = root;
- int[] prefixofsuffix = generatefunction(p);
- int k = -1;
- int ii = 0;
- map.put(-1, root);
- for(int i = 0;i<t.length();i++){
- //System.out.println(t.charAt(i));
- temp.child = new Node(t.charAt(i));
- temp.child.parent = temp;
- temp = temp.child;
- map.put(ii,temp);
- while(k > -1 && p.charAt(k+1)!=t.charAt(i)){
- k = prefixofsuffix[k];
- }
- if(p.charAt(k+1)==t.charAt(i)){
- k++;
- }
- temp.k = k;
- if(k==p.length()-1){
- //System.out.println(ii);
- temp = map.get(ii-p.length());
- //map.get(-69);
- //System.out.println(temp.c);
- temp.child = null;
- k = temp.k;
- ii -= p.length();
- //System.out.println(ii);
- }
- ii++;
- }
- return root;
- }
- public static int[] generatefunction(String p){
- int[] prefixofsuffix = new int[p.length()];
- int k = -1;
- prefixofsuffix[0] = -1;
- for(int i = 1;i<p.length();i++){
- while(k>-1 && p.charAt(k+1)!=p.charAt(i)){
- k = prefixofsuffix[k];
- }
- if(p.charAt(k+1)==p.charAt(i)){
- k++;
- }
- prefixofsuffix[i] = k;
- }
- return prefixofsuffix;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement