Cod sursa(job #1757511)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 15 septembrie 2016 10:38:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <fstream>
#include <cstring>
#define DIM 2000001
using namespace std;
char t[DIM],b[DIM];
int s[DIM],p[DIM],i,j,n,m,nr,l;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int main (){

    fin>>t+1;
    n = strlen (t+1);
    l = 0;
    for (i=2;i<=n;i++){
        while (l!=0 && t[i]!=t[l+1])
            l = p[l];
        if (t[i]==t[l+1])
            l++;
        p[i] = l;
    }
    fin>>b+1;
    m = strlen (b+1);
    l =  0;
    for (i=1;i<=m;i++){
        while (l!=0 && b[i]!=t[l+1])
            l = p[l];
        if (b[i] == t[l+1])
            l++;
        if (l == n){
            s[++nr] = i-n;
            l = p[l];
        }
    }
    fout<<nr<<"\n";
    if (nr <= 1000){
        for (i=1;i<=nr;i++)
            fout<<s[i]<<" ";
    }
    else{
        nr = 1000;
        for (i=1;i<=nr;i++)
            fout<<s[i]<<" ";
    }

    return 0;
}
/*#include <fstream>
#include <cstring>
using namespace std;
int n,m,i,nr[1010],j,ap,ok,k;
char v[2000001],w[2000001],x;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

int main (){


    fin>>v;
    fin>>w;
    n = 0;
    while ((v[n]>='0'&&v[n]<='9')||(v[n]>='a'&&v[n]<='z')||(v[n]>='A'&&v[n]<='Z'))
        n++;
    m = 0;
    while ((w[m]>='0'&&w[m]<='9')||(w[m]>='a'&&w[m]<='z')||(w[m]>='A'&&w[m]<='Z'))
        m++;
    /*n = strlen (v);
    m = strlen (w);
/*    for (i=0;i<n;i++)
        fout<<v[i];
    fout<<"\n";
    for (i=0;i<m;i++)
        fout<<w[i];
*/
  /*  k = 0;
    for (i=0;i<m;i++){
        if (w[i] == v[k]){
            k++;
            if (k == n){
                ap++;
                if (ap <= 1000)
                    nr[ap] = i-n+1;
                k = 0;
                i -= n;
                i++;
            }
        }
        else
            k = 0;
    }
    fout<<ap<<"\n";
    if (ap <= 1000){
        //ap = 1000;
        for (i=1;i<=ap;i++)
            fout<<nr[i]<<" ";
    }
    return 0;
}*/