Cod sursa(job #2460906)

Utilizator FrostfireMagirescu Tudor Frostfire Data 24 septembrie 2019 17:48:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#define NMAX 2000000

using namespace std;

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

int phi[2*NMAX+10], nr;
string s, s1, s2;
vector <int> sol;

int main()
{
    f >> s1 >> s2;
    s = s1 + '*' + s2;
    phi[0] = -1;
    for(int i=1; i<s.size(); i++)
        {   int x = i - 1;
            while(s[phi[x]+1] != s[i] && phi[x] != -1) x = phi[x];
            if(s[phi[x]+1] == s[i]) phi[i] = phi[x] + 1;
            else phi[i] = -1;
        }
    int n = s1.size();
    for(int i=n; i<s.size(); i++)
        if(phi[i] == n-1)
            {   nr++;
                if(nr <= 1000) sol.push_back(i-2*n);
            }
    g << nr << '\n';
    for(int i=0; i<sol.size(); i++) g << sol[i] << ' ';
    g << '\n';
    return 0;
}