Cod sursa(job #2351775)

Utilizator RazvanPanaiteRazvan Panaite RazvanPanaite Data 22 februarie 2019 18:03:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
#define DMAX 2000010

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[DMAX],b[DMAX];
int vala[DMAX],valb[DMAX];

vector <int> sol;

int k,n,m,solutii;

void citire();

int main()
{int i;
 citire();
 k=0;
 n=strlen(a+1);
 for(i=2;i<=n;i++)
    {while(a[k+1]!=a[i] && k)
           k=vala[k];
     if(a[k+1]==a[i])
        k++;
     vala[i]=k;
    }
 m=strlen(b+1);
 if(b[1]==a[1])
    {valb[1]=1;
     k=1;
    }
    else
    k=0;
 for(i=2;i<=m;i++)
     {while(a[k+1]!=b[i] && k)
            k=vala[k];
      if(a[k+1]==b[i])
         k++;
      valb[i]=k;
      if(k==n && sol.size()<1000)
         {sol.push_back(i-n);
          solutii++;
         }
         else
         if(k==n)
            solutii++;

     }
 fout<<solutii<<'\n';
 for(i=0;i<sol.size();i++)
     fout<<sol[i]<<' ';
 fout<<'\n';
 return 0;
}
void citire()
{fin>>a+1;
 fin>>b+1;
}