Cod sursa(job #2266813)

Utilizator vadim171098vadim pislari vadim171098 Data 22 octombrie 2018 21:39:37
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

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

int getz(string str, int Z[],int len)
{
    int n = str.length();
    int L, R, k;
    int sum= 0;
    L = R = 0;
    for (int i = 1; i < n; ++i){
        if (i > R){
            L = R = i;
            while (R<n && str[R-L] == str[R]) R++;
            Z[i] = R-L;
            R--;
        }
        else{
            k = i-L;
            if (Z[k] < R-i+1)
                Z[i] = Z[k];
            else{
                L = i;
                while (R<n && str[R-L] == str[R])R++;
                Z[i] = R-L;
                R--;
            }
        }
        if(Z[i] == len)sum++;
    }
    return sum;
}

void str(string text, string sch)
{
    string imp = sch + "#" + text;
    int l = imp.length(),len =sch.length();

    int Z[l];
    int dim = getz(imp, Z,len);
    out<<dim<<endl;
    for (int i = 0; i < l; ++i)
    {
        if (Z[i] == sch.length())
            out << i - len -1 << " ";
    }
}


int main()
{
    string sch,text;
    in>>sch>>text;
    str(text, sch);
    return 0;
}