Cod sursa(job #2449189)

Utilizator StanCatalinStanCatalin StanCatalin Data 18 august 2019 16:08:01
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
/// Z
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int dim = 2000005;

string s1,s2;
vector <int> omg;
int l,r,z[dim];

int main()
{
    in >> s1 >> s2;
    s2 = s1 + s2;
    int l = 0,r = 0;
    int n = s2.length();
    for (int i=1; i<n; i++)
    {
        if (i > r)
        {
            l = i;
            r = i;
            while (r < n && s2[r] == s2[r-l])
            {
                r++;
            }
            z[i] = r-l;
            r--;
        }
        else
        {
            if (z[i-l] < r-l+1)
            {
                z[i] = r-l+1;
            }
            else
            {
                l = i;
                while (r < n && s2[r] == s2[r-l])
                {
                    r++;
                }
                z[i] = r-l;
                r--;
            }
        }
    }
    int cnt = 0;
    for (int i=1; i<n; i++)
    {
        if (s2[i] == s1[0] && z[i] == s1.length())
        {
            cnt++;
            omg.push_back(i);
        }
    }
    out << cnt << "\n";
    for (int i=0; i<omg.size(); i++)
    {
        out << omg[i] - s1.length() << " ";
    }
    return 0;
}