Cod sursa(job #2460505)

Utilizator FrostfireMagirescu Tudor Frostfire Data 23 septembrie 2019 20:20:50
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];
string s, s1, s2;
vector <int> sol;

int main()
{
    f >> s1 >> s2;
    s = s1 + '#' + s2;
    int i=1, j=0;
    while(i < s.size())
        {   if(s[i] == s[j])
                {   j++;
                    phi[i] = j;
                    i++;
                }
            else
                {   if(j) j = phi[j-1];
                    else i++;
                }
        }
    for(int i=0; i<s.size(); i++) if(phi[i] == s1.size()) sol.push_back(i-2*s1.size());

    g << sol.size() << '\n';
    int l = sol.size();
    l = min(1000, l);
    for(int i=0; i<l; i++) g << sol[i] << ' ';
    g << '\n';
    return 0;
}