You have a very large document, for an instance the document containing 1 million words. You are given a huge file, which contains list of 1 million w

You have a very large document, for an instance the document containing 1 million words. You are given a huge file, which contains list of 1 million words (includes multi-word strings). Give an algorithm/datastructure which returns the positions of the words/multiwords occurring in document which exist in the list given.

Example:
given document (which can be upto 1 million words):

I am xyz who did my bachelors from Aab Bbc Ccd Dde university. I like solving puzzles like Albert Einstein used to.

given list:

Albert Einstein
Abdul Kalam
Aab Bbc Ccd Dde
Massachusetts Institute of Technology
xyz
so no...upto million words

Result:
Word position:

3 (xyz)
9-12 (Aab Bbc Ccd Dde)
19-20 (Albert Einstein)
The basic idea is suffix tree, if the memory is not big enough, build the suffix array which is sorted, then sort the word list if it is unsorted, do the merge to two lists to find matching words
O(nlongn)

There are two sentences. Find the common words in the two sentences.

There are two sentences. Find the common words in the two sentences.

using suffix trees or suffix array based on words (find common sub-sentences )
use hash table
sort two sentences and merge

Write a function to find the longest palindrome from a string.

Write a function to find the longest palindrome from a string.

Suppose the string is str, you reverse the str get strr, make a suffix tree for these two strings. If palindrome is like “cabbad”, for every i find LCA of suffix i of str and suffix m-i+1of strr
If palindrome is like “dacab”, for every i find LCA of suffix i of str and suffix m-i of strr
Find maximal LCA, this O(n)
or
Use dynamic programming, find longest common substring with str and strr, O(n^2)
This is not right
forward T: ABCXYYZCBA
reverse T: ABCZYYXCBA
The longest common substring is ABC, but the longest palindromic substring is just YY.

Create an efficient (time and memory wise) for the following:

Create an efficient (time and memory wise) for the following:
You have a dictionary of names of phone numbers. As a user is searching for a name it should show all possible combinations.
For example. As user types 'D' it should show all names beginning with D. And then when user types 'a', it should show all names beginning 'Da' etc. Something like Google sense does. So at each point of time show end users the possible combinations.
Part II. The string could be random in nature and user need not begin at the start. For example, in the name Daniel, the user can give string 'nie' and the algorithm should show all names in the dictionary with substring 'nie' which of course will include 'Daniel' and many others. You have to design a memory and time inexpensive operation.

For the first problem, a prefix tree is the most optimal solution.
For the second problem, a suffix tree might be what you need.

having a string say, "foobarfoo", in which "fo" and "oo" are repeated twice. You have to find all such repeated pairs whose length is tow in O(n) time

having a string say, "foobarfoo", in which "fo" and "oo" are repeated twice. You have to find all such repeated pairs whose length is tow in O(n) time. The string can only have alphanumeric elements in it and code it in C.

Use suffix tree O(n) which is not easy to code
Use dp which is O(n^2)
Use hash table, it can be done in O(n).
Traverse the string, each time take two consecutive characters, hash them in the hashtable, the hash function is just base 36 number system

void foo(char* str)
{
 int i=0;
 int j=1;
 int hashtable[1296]={0};//36*36
 while(str[j])
 {
  int idx=(str[i]-'a')*36+(str[j]-'a');//base 36
  if(!hashtable[idx])
   hashtable[idx]=1;
  else cout<<str[i]<<str[j]<<endl;
  i++;
  j++;
 }
}