Cod sursa(job #1096856)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 2 februarie 2014 17:47:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<fstream>
#include<string>
using namespace std;
int i,n,m,z[4000005],sol[1005],nr,l,r;
string s, s1;

int main(void) {
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    getline(fin,s); s=' '+s;
    m=s.length()-1;
    
    getline(fin,s1);
    s+='$'+s1;
    n=s.length();
    
    l=r=0;
    
    for (i=2; i<n; ++i) {
     
     if (i>r) {
              int p1=1,p2=i,lung=0;
              while (s[p1]==s[p2]) { ++p1; ++p2; ++lung; }
              --p1; --p2;
              z[i]=lung;
              if (lung>0) { l=i; r=p2; }
              }
     else {
          int poz=i-l+1, dep=r-i+1;
          if (z[poz]<dep) z[i]=z[poz];
           else {
                int p1=dep+1, p2=r+1, lung=dep;
                while (s[p1]==s[p2]) { ++p1; ++p2; ++lung; }
                --p1; --p2;
                z[i]=lung;
                l=i;
                r=p2;
                }
           }
     
     if (z[i]==m) {
                  ++nr;
                  if (nr<=1000) sol[nr]=i-m-2;
                  }
     
     }
    
    fout<<nr<<"\n";
    
    for (i=1; i<=min(nr,1000); ++i) fout<<sol[i]<<" ";
 return(0);
}