Cod sursa(job #2713204)

Utilizator Florinos123Gaina Florin Florinos123 Data 27 februarie 2021 13:58:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

#define N 2000005
#define mod 1000003

int p, t;

int n, m, k;

char txt[N], pat[N];

int sol[N];

char Val (char s)
{
    if (s >= 'a' && s <= 'z')
        return s - 'a' + 1;
    return s - 'A' + 1;
}

int main()
{
    f >> pat >> txt;
    n = strlen(txt); m = strlen(pat);

    for (int i=0; i<m; i++)
    {
        p = (1LL * p + Val(pat[i])) % mod;
        t = (1LL * t + Val(txt[i])) % mod;
    }

    for (int i=0; i<=n-m; i++)
    {
        if (p == t)
        {
            int cnt = 0;
            for (int j=0; j<m; j++)
            {
                if (pat[j] != txt[i+j]) break;
                cnt ++;
            }

            if (cnt == m && k  < 1000) {
                k ++; sol[k] = i;
            }
        }

        if (i < n - m)
        {
            t = (1LL * t - Val(txt[i])) % mod;
            t = (1LL * t + Val(txt[i+m])) % mod;
        }
    }

    g << k << "\n";
    for (int i=1; i<=k; i++)
        g << sol[i] << " ";

    return 0;
}