nicuvlad76

Untitled

Dec 4th, 2020
470
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. ifstream fin("lant2.in");
  4. ofstream fout("lant2.out");
  5. const short Cuvmax=35;
  6. const short Nrdist=160;
  7. const int Pmax=1005;
  8. char s[Pmax],a[Nrdist][Cuvmax],*p,sep[] = " ,:;.!?-";;
  9. int k,n,grad[Nrdist],S[Nrdist],gradcpy[Nrdist];
  10. vector<short>L[Nrdist+105];
  11. queue<int>Q;
  12. inline void Read()
  13. {
  14.     fin>>k;
  15.     fin.get();
  16.     n=0;
  17.     while (fin.getline(s,1001))
  18.     {
  19.         p=strtok(s,sep);
  20.         ///separam textul de ,:;.!? etc
  21.         while (p!=NULL)
  22.         {
  23.             bool ok=false;
  24.             for (int i=1; i <= n && !ok; ++i)
  25.                 if (strcmp(p,a[i])==0)
  26.                     ok=true;
  27.             if (!ok)
  28.             {
  29.                 ++n;
  30.                 strcpy(a[n],p);
  31.             }
  32.             p=strtok(NULL,sep);
  33.         }
  34.     }
  35. }
  36. inline int Levenshtein(const char b[],const char c[])
  37. {
  38.     ///dp[i][j]-numarul minim de operatii de a transforma primele  i caractere din b[i]
  39.     ///         in primele j caractere din c[i]
  40.     int X,Y,dp[Cuvmax][Cuvmax];
  41.     X=strlen(b);
  42.     Y=strlen(c);
  43.     ///Initializari:
  44.     for(int i=0; i<=X; i++)
  45.         dp[i][0]=i;
  46.     for(int i=0; i<=Y; i++)
  47.         dp[0][i]=i;
  48.     for(int i=0; i<X; i++)
  49.         for(int j=0; j<Y; j++)
  50.         {
  51.             dp[i+1][j+1]=min(1+dp[i][j+1],1+dp[i+1][j]);
  52.             if(b[i]==c[j] && dp[i+1][j+1]>dp[i][j])///move
  53.                 dp[i+1][j+1]=dp[i][j];
  54.         }
  55.     return dp[X][Y];
  56. }
  57. inline void Solve()
  58. {
  59.     for(int i=1; i<n; i++)
  60.         for(int j=i+1; j<=n; j++)
  61.             if(Levenshtein(a[i],a[j])<=k)
  62.             {
  63.                 ++grad[j];
  64.                 ++gradcpy[i];
  65.                 L[i].push_back(j);
  66.             }
  67.     S[1]=1;
  68.     for(int i=1; i<=n; i++)
  69.         if(!grad[i])
  70.             Q.push(i);
  71.     while(!Q.empty())
  72.     {
  73.         int varf=Q.front();
  74.         Q.pop();
  75.         for(unsigned int j=0;j<L[varf].size();j++)         ///aflu numarul de lanturi de la nodul 1 la nodul i
  76.         {
  77.             int w=L[varf][j];
  78.             S[w]+=S[varf];
  79.             --grad[w];
  80.             if(!grad[w])
  81.                 Q.push(w);
  82.         }
  83.     }
  84.     long long sol=0;
  85.     for(int i=1; i<=n; i++)
  86.         if(!gradcpy[i])
  87.             sol+=S[i];  ///in varful i se opreste lantul(varful nu mai are adiacenti)
  88.     fout<<sol<<"\n";
  89. }
  90. int main()
  91. {
  92.     Read();
  93.     Solve();
  94.     fin.close();
  95.     fout.close();
  96.     return 0;
  97. }
RAW Paste Data