Cod sursa(job #501392)

Utilizator buburuzaLaura S buburuza Data 14 noiembrie 2010 21:18:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#include<string.h>
#include<vector>

using namespace std;


#define pb push_back 

vector <int> v;
vector <int> :: iterator it;

int pi[2000005];

char a[2000005],b[2000005];
 
 
int main()
{
    int i,sw,n,m,cnt=0;
     
    ifstream f("strmatch.in");
    f>>a>>b;
    n=strlen(a);
    m=strlen(b);
    
   pi[0]=0;
    for (i=1;i<n;i++)
   {
        sw=pi[i-1];
       while (sw>0 && a[i]!=a[sw])
            sw=pi[sw-1];
        if (a[i]==a[sw])
           pi[i]=sw+1;
       else
            pi[i]=0;
    }
     
     
    
    sw=0;
    for (i=0;i<m;i++)
    {
        while (sw>0 && b[i]!=a[sw])
            sw=pi[sw-1];
        if (b[i]==a[sw])
            sw++;
        if (sw==n)
        {
            ++cnt;
           sw=pi[sw-1];
           if (cnt<=1000) v.pb(i+1-n) ;
       }
   }
     
    ofstream g("strmatch.out");
    g<<cnt<<'\n';
     
    for (it=v.begin();it<v.end();++it)
        g<<*it<<' ';
     
    f.close();
    g.close();
   return 0;
}