Beh...
(1) Con un costo O(n log n) [in-place mergesort, senza altre strutture dati] ti ordini i tuoi vettori, ognuno per ogni parola.
(2) Poi inizi a scorrere i tuoi m vettori dall'inizio alla fine, usando m cursori e confrontando i valori. Ad ogni step aumenti il cursore del vettore il cui elemento è il minore degli m.
(3) Quando tutti gli m cursori sono su valori uguali, allora inserisci in un nuovo array il risultato.
Esempio
ORIGINALE:
pippo: 3 5 1 4
paperino: 4 1
pluto: 4 3 5
DOPO L'ORDINAMENTO:
pippo: 1 3 4 5
paperino: 1 3
pluto: 3 4 5
PASSO 1:
pippo:
1 3 4 5
paperino:
1 3
pluto:
3 4 5
uguali: -
PASSO 2:
pippo: 1
3 4 5
paperino:
1 3
pluto:
3 4 5
uguali: -
PASSO 3:
pippo: 1
3 4 5
paperino: 1
3
pluto:
3 4 5
uguali: 3
Qui addirittura puoi alzare tutti e tre i cursori, dato che l'uguaglianza già c'è
Spero di essermi spiegato, e di avere capito il problema.
Costo dell'approccio: O(n log n) + O(n) = O(n log n)