#include <iostream>
#include <string>
#include <cassert>
using namespace std;

class Node;
class List;

class Iterator
 {public:
   Iterator();
   string get() const;
   Iterator next()const;
   Iterator previous()const;
   bool equals(Iterator b) const;
   bool is_null() const;
  private:
   Node* position;
  friend class List;
 };

class List
{public:
   List();
   void push_back(string s);
   void insert(Iterator p, string s);
   void erase(Iterator p);
   bool presente();
   bool empty() const;
   Iterator begin();
   Iterator end();
 private:
   Node* first;
   Node* last;
};

class Node
 {public:
   Node(string s);
  private:
   string data;
   Node* prec;
   Node* succ;
  friend class List;
  friend class Iterator;
 };

Node::Node(string s)
  {data = s;
   prec = NULL;
   succ = NULL;
  }

Iterator::Iterator()
  {position = NULL;
  }

string Iterator::get() const
  {
assert(position != NULL);
   return position->data;
  }

bool Iterator::equals(Iterator b) const
  {
   return position == b.position;
  }


Iterator Iterator::next() const

{
assert(position != NULL);

 Iterator t;

 t.position = position->succ;

 return t;

}




Iterator Iterator::previous() const

{
  assert(position != NULL);

    Iterator t;

    t.position = position->prec;

    return t;

}


bool Iterator::is_null() const
  {return position==NULL;
  }

List::List()
  {first = NULL;
   last = NULL;
  }

bool List::empty() const
  { return first==NULL; }

Iterator List::begin()
  {Iterator i;
   i.position = first;
   return i;
  }

Iterator List::end()
  {Iterator i;
   i.position = last;
   return i;
  }

void List::push_back(string s)
{Node* n = new Node(s);
   if (last == NULL)
  {first = n;
   last = n;
  }
else  {n->prec = last;
        last->succ = n;
       last= n;
      }
}

void List::insert(Iterator p, string s)
{if (empty())
    push_back(s);
 else {Node* n = new Node(s);
       Node* dopo = p.position;
       Node* prima = dopo->prec;
       n->prec = prima;
       n->succ = dopo;
       dopo->prec = n;
       if (prima==NULL)
          first = n;
       else prima->succ = n;
      }
}

void List::erase(Iterator p)
{assert (p.position != NULL);
 Node* rimuovi = p.position;
 Node* dopo = rimuovi->succ;
 Node* prima = rimuovi->prec;
 if (prima==NULL)
    first = dopo;
 else prima->succ = dopo;
 if (rimuovi==last)
  last = prima;
 else dopo->prec = prima;
 delete rimuovi;
}

const int N = 4;

List prefisso(List a[N],const int N,string s)
{
    Iterator p;
    List aus;
    int i,l1=s.length();

    for(i=0;i<N;i++)
    {
        for(p=a[i].begin();!p.is_null();p=p.next())
        {
            string s1=p.get();
            if(s1.substr(0,l1)==s)
            {
                aus.push_back(s1);
            }
        }

    }
    return aus;
}

int main()
{
    List risultato;
    string s="io";
    int m,i,j;
    string nome, name;
    List a[N];

    for( i=0;i<N;i++)
    {
        cout<<"Inserisci Numero membri\n";
        cin>>m;
        for(j=0;j<m;j++)
        {
            cout<<"Inserisci Nome membro \n";
            cin>>nome;
            a[i].push_back(nome.c_str());
        }
    }

    risultato=prefisso (a,s);
    Iterator pos;

    if(!risultato.empty())
    {
        cout<<"Le stringhe della lista con prefisso " << s << " sono : ";

        for(pos=risultato.begin();!pos.is_null();pos=pos.next())
        cout<<pos.get()<<endl;
    }

return 0;
}