Cod sursa(job #1897052)

Utilizator ifrimencoAlexandru Ifrimenco ifrimenco Data 1 martie 2017 09:22:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#define nmax 2000002
#define mmax 2000002
using namespace std;
char t[nmax], p[nmax];
int urm[nmax];
int n, m;
vector <int> poz;
void urmatorul(char *p)
{
    int k=-1, x;
    urm[0]=0;
    for (x=1; x<m; x++)
    {
        while (k>0 &&  p[k+1]!=p[x]) k=urm[k];
        if (p[k+1]==p[x]) k++;
        urm[x]=k;
    }
}
int main()
{
    int i, x=-1;
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f.getline(p,2000001);
    f.getline(t,2000001);

    n=strlen(t);
    m=strlen(p);
    urmatorul(p);
    for (i=1; i<=n; ++i)
   for (i=0; i<n; ++i)
   {
       while (x>0 && p[x+1]!=t[i] ) x=urm[x];
       if (p[x+1]==t[i]) x++;
       if (x==m-1) poz.push_back(i-m+1);

   }
   g << poz.size() << "\n";
   vector <int> :: iterator it;
   for (it=poz.begin();it!=poz.end();++it)
        if (distance(poz.begin(),it) <=1000) g << *it << " ";
   else break;
    return 0;
}