Cod sursa(job #845022)

Utilizator S7012MYPetru Trimbitas S7012MY Data 30 decembrie 2012 12:56:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <algorithm>
#include <string>
using namespace std;

string a,b;
int z[4000000],l,r,k,m,poz[1001],sz;

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f>>a>>b;
    m=a.size();
    a+='$'; a.append(b);
    int n=a.size();
    for(int i=1; i<n; ++i) {
      if(i>r) {
        l=r=i;
        for(;r<n && a[r-l]==a[r];++r);
        z[i]=r-l; --r;
      }else {
        int k=i-l;
        if(z[k]<r-i+1) z[i]=z[k];
        else {
          l=i;
          for(;r<n && a[r-l]==a[r];++r);
          z[i]=r-l; --r;
        }
      }
      if(z[i]==m && sz<=1000) poz[++sz]=i-m-1;
    }
    g<<sz<<'\n';
    for(int i=1; i<=sz; ++i) g<<poz[i]<<' ';
    return 0;
}