CareerCup

The trick is to first replace all the input strings with something unique and non-colliding. So my opinion is to hash each string into a unique value, such as: input[0].hashCode() and surround that with single quotes. This should not cause collision. Then, replace all the occurrences of inputs in the text with their hashed value. And finally replace the hashed values with the replacement values.

Working example:

public class Main {
	
		public static void main(String[] args) {
			
			String[] inputs = {"teh", "quick", "rown", "Fox", "jmuped"};
			String[] replacements = {"the", "quick b", "rown ", "fox", "jumped"};
			
			String input = "teh quickrownFox jmuped over the lazy dog";
			
			letsGo(input, inputs, replacements);
		}
	
		public static void letsGo(String input, String[] inputs, String[] replacements){
			System.out.println("start: " + input);
			String[] hashes = new String[5];
			for(int i=0; i<inputs.length; i++){
				hashes[i] = "'"+inputs[i].hashCode()+"'";
			}
			for(int i=0; i<inputs.length; i++){
				String str = inputs[i];
				String replacement = hashes[i];
				input = input.replaceAll(str, replacement);
			}
			System.out.println("hashed: " + input);
			for(int i=0; i<inputs.length; i++){
				String str = hashes[i];
				String replacement = replacements[i];
				input = input.replaceAll(str, replacement);
			}
			System.out.println("final: " + input);
		}
	}

#!/bin/sh
sed '1,$ {
        s/'"$1"'/SED_FOO_1/g
        s/'"$2"'/SED_FOO_2/g
        s/'"$3"'/SED_FOO_3/g
        s/'"$4"'/SED_FOO_4/g
        s/'"$5"'/SED_FOO_5/g
        s/SED_FOO_1/'"$6"'/g
        s/SED_FOO_2/'"$7"'/g
        s/SED_FOO_3/'"$8"'/g
        s/SED_FOO_4/'"$9"'/g
        s/SED_FOO_5/'"${10}"'/g
}'

./amazon.sh black night white day hose white day black night sprinkler < test.txt

Simply scan for each input and make an in-place replacement in a string buffer. Should have a complexity of ~O(5n) or simply O(m*n) where m is the number of inputs to replace and n is the length of the body text. Average case will be faster... perhaps Θ(3n).

public static String replaceByLookup(String[] input, String[] replace, String text) {
        StringBuilder buf = new StringBuilder(text);
        int pos = 0;
        while (pos < buf.length()) {
            boolean madeReplacement = false;
            for (int i = 0; i < input.length; i++) {
                if (pos + input[i].length() > buf.length())
                    continue;
                if ( input[i].equals(buf.substring(pos, pos + input[i].length())) ) {
                    buf.replace(pos, pos + input[i].length(), replace[i]);
                    pos += replace[i].length();
                    madeReplacement = true;
                    break;
                }
            }
            if (! madeReplacement)
                pos++;
        }
        return buf.toString();
    }

public class StringMatch {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] input = new String[5];
		String[] replace = new String[5];
		
		input[0] = "hello";
		input[1] = "is";
		input[2] = "madara";
		input[3] = "luffy";
		input[4] = "tobi";
		
		replace[0] = "hi";
		replace[1] = "was";
		replace[2] = "itachi";
		replace[3] = "dragon";
		replace[4] = "obito";
		boolean flag = false;
		String text = new String();
		text = "hello is madara there? this is tobi here";
		Scanner sc = new Scanner(text);
		String inp;
		StringBuilder out = new StringBuilder();
		while(sc.hasNext()){			
			inp = sc.next();
			for(int i=0; i<input.length;i++){
				flag = false;				
				if(inp.compareTo(input[i])==0){
					inp = replace[i];
					out.append(inp);
					out.append(" ");					
					break;
				}else{
					flag = true;
					continue;
				}					
			}
			if(flag){
				out.append(inp);
				out.append(" ");				
			}			
		}
		System.out.print(out);
	}
}

Use Trie data-structure to get O(n) of complexity.

class TrieNode {
public:
  TrieNode *next[256];
  char *repStr;
  TrieNode() {
    memset(next, 0, sizeof(next));
    rep_str = NULL;
  }
  ~TrieNode() {
    for (i = 0; i < 256; ++i) {
      if (next[i]) {
        delete next;
      }
    }
  }
};

TrieNode *buildTree(char **rep, char** repWith) {
  TrieNode *root = new TrieNode;
  for (int i = 0; rep[i] != NULL; i++) {
    char *c = rep[i];
    TrieNode *curr = root;
    while (*c != '\0') {
      if (curr->next[(unsigned)*c] == NULL) {
        curr->next[(unsigned)*c] = new TrieNode;
      }
      curr = curr->next[unsigned)*c];
    }
    curr->repStr = repWith[i];
  }
}

char * ReplaceStr(char *orig, char **rep, char **repWith) {
  char *buffer = new char[strlen(orig) + 1];
  int size = strlen(orig) + 1;
  int write = 0;

  TrieNode *root = buildTree(rep, repWith);
  int depth = 0;
  TrieNode *curr = root;

  while (*orig != '\0') {
    buffer[write++] = *orig;
    curr = curr->next[(unsigned)*rep];
    depth++;
    if (curr == NULL) {
      curr = root;
      depth = 0;
    } else if (curr->repStr != NULL) {
      write -= depth;
      char *c = curr->repStr;
      while (*c != '\0') {
        buffer[write++] = *c
      }
    }
  }
}