Текущ брой на Списание ИнфоМан
 


Балканска олимпиада по информатика 2005, Задача 2.3. WORD COUNTING

Уловието на задачата може да прочетете тук.

Решение

За решението на тази задача ще се използва алгоритъмът на Кнут-Морис-Прат (КМП), с помощта на който могат да се намерят всички срещания на даден стринг в друг стринг със сложност O(N+M), като Nе дължината на търсения стринг P, а е дължината на стринга, в който търсимT. Тук първо ще бъде описан този алгоритъм, а след това как той може да се използва, за да се реши дадената задача.

КМП се състои от две главни части. В първата част се пресмята за всеки префикс на стринга P кой е най-дългият префикс на P различенот S, който е суфикс на S. Тази информация се използва във втората част, където се намират всички срещания на P в T.

За да се пресметне информацията от първата част се дефинира функция F(i), която за префикса на P, който е дълъг iсимвола, връща колко е дълъг най-големия префикс различен от P[1]..P[i], който е суфикс на P[1]..P[i]. Вижда се, че F(1) = 0. За да се пресметне F(k)се проверява колко е стойността за F(k-1). Нека P[i] e i-тия символ на P. Проверяваме дали P[F(k-1)+1] e равен на P[k]. Ако е така, то F(k) = F(k-1)+1. В противен случай се проверява дали P[F(F(k-1))+1] е равен на P[k]. Ако това е така, то F(k) = F(F(k-1))+1. Ако не, се продължава нататък или докато се получи съвпадение, или докато се окаже, че няма такъв префикс. Тогава F(k) = 0. Идеята на това обхождане е, че като е пресметнат търсеният суфикс L за дадена позиция, за следващата ще отговаря същия суфикс, като на него се добави още една буква ако тя съвпада, ако не съвпада, се разглежда суфикса Lи се проверява пресметнатата за него стойност по същия начин и т.н.

Във втората част се използват пресметнатите стойности от първата част. Основната идея е вече пресметната информация да се използва и по-нататък, а не да се пресмята отново. За да се намерят всички срещания на в Tсе прилага логиката описана по-долу. Започва се със сравняване на първите символи на и T. Нека имаме два брояча и t, като pпоказва кой символ от Pсе разглежда, а tпоказва това за T. В началото p = 1и t = 1. Ако в даден момент от сравняването на двата стринга се получи разминаване, то p става равно на F(p-1)+1 ако p не е първия символ на P, а ако е – то p = p+1. Идеята на това е че ако на дадена позиция има разминаване, се “приплъзва” така, че най-дългият префикс, който е суфикс на префикса с дължина p-1 и е различен от него се поставя така, че десният му край съвпада с позиция t-1 и сравняването продължава.

Това е показно на фигурата, където Т=”alabortoortokala”, а P=ortoorte”В дадена ситуация, ако сравняваме позиции 12 на и 8 на се получава разлика. Тогава се “приплъзва” така, че 12-та позиция на Tсе сравнява с 4-тапозиция на P, защото F(7) = 3.Тоест ort” е най-големия префикс, който е суфикс на “ortoort”и е различен от него, Сега сравняването продължава като t = 12 и p = 4. Със сиво са показани позициите, където се получава разминаване между двата стринга.

 

Така се намират всички срещания на P  в с помощта на алгоритъма на Кнут-Морис-Прат със сложност O(M+N), като първата част има сложност O(M), а втората – O(N).

Сега остава да се опише как този алгоритъм може да се използва в дадената задача. Обхожда се дървото в дълбочина и за всяко ребро се пуска КМП, като за всеки връх се помни при изпълнението на алгоритъма по реброто, което идва от родителя му, на коя позиция от Pе бил броячът p. Когато се продължава по ребра, излизащи от деден връх, този брояч не приема стойност 1, а тази, която е записана в дадения връх. По този начин се обхожда дървото и се намират всички срещания на търсената дума в него.

Примерна реализация

#include <fstream>
#include <string>
#include <vector>
#define MAXN 15002
#define MAXLEN 1002
using namespace std;

 int n;
 // this vector keeps the children of a vertice
 vector<int> a[MAXN];
 // this vector keeps the word on the edge to a child of a vertice
 vector<string> b[MAXN];
 int len;
 int p[MAXLEN];
 string s;
 int res;
 ifstream f1 ("wordcount.in");
 ofstream f2 ("wordcount.out");

 // makes the precomputing for the KMP algorithm
 void prefix ()
 {
  int i,c,q;
  q=0;
  len=s.size();
  for (i=2;i<=len;i++)
   {
    while (q!=0 && s[q]!=s[i-1])
     q=p[q];
    if (s[q]==s[i-1]) q++;
    p[i]=q;
   }
 }

 // makes the KMP algorithm for a given edge in the tree
 int go (string a,int q)
 {
  int i,c;
  c=a.size();
  for (i=1;i<=c;i++)
   {
    while (q!=0 && a[i-1]!=s[q])
     q=p[q];
    if (a[i-1]==s[q])
     q++;
    if (q==len)
     {
      res++;
      q=p[q];
     }
   }
  return q;
 }

 // makes the depth-first search through the tree
 void dfs (int i,int fat,int q)
 {
  int j,c;
  c=a[i].size();
  for (j=c-1;j>=0;j--)
   if (a[i][j]!=fat)
    dfs(a[i][j],i,go(b[i][j],q));
 }

 int main ()
 {
  int i,p,q;
  f1 >> n;
  for (i=1;i<n;i++)
   {
    f1 >> p >> q >> s;
    a[p].push_back(q);
    b[p].push_back(s);
   }
  f1 >> s;
  prefix();
  dfs(0,-1,0);
  f2 << res << endl;
  return 0;
 }



Автор: Ростислав Руменов и Антон Димитров


обратно към брой 27