Cod sursa(job #1578344)

Utilizator UMihneaUngureanu Mihnea UMihnea Data 24 ianuarie 2016 11:40:31
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <string>
#include <vector>
#define N 2000010

using namespace std;

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

string a, b;
vector< int > sol;
int z[N], n, m, i, j, k, L, R, cnt;

int main()
{
    f >> b ;
    f >> a;

    n = a.size();
    m = b.size();
    for(i = 1; i < m; i++)
    {
        if(i > R)
        {
            for(j = 0, k = i; b[j] == b[k] && k < m; k++, j++);
            z[i] = j;
            L = i;
            R = i+j-1;
            continue;
        }
        j = i-L;
        if(i+z[j]-1 < R)
        {
            z[i] = z[j];
            continue;
        }
        for(k = R+1, j = R-L+1; b[j] == b[k] && k < m; k++, j++);
        z[i] = j;
        L = i;
        R = i+z[i]-1;

    }
    R = -1;L=0;
    for(i = 0; i < n; i++)
    {
        if(i > R)
        {
            for(j = 0, k = i; b[j] == a[k] && k < n; k++, j++);
            L = i;
            R = k-1;
            if(R-L+1 == m)
            {
                cnt++;
                if(cnt <= 1000)
                    sol.push_back(L);
            }
            continue;
        }
        j = i-L;
        if(i+z[j]-1 < R)
            continue;
        for(k = R+1, j = R-L+1; b[j] == a[k] && k < n; k++, j++);
        L = i;
        R = k-1;
        if(R-L+1 == m)
        {
            cnt++;
            if(cnt <= 1000)
                sol.push_back(L);
        }
    }
    g << cnt << '\n';
    for(auto it : sol)
        g << it << ' ';
    return 0;
}