Cod sursa(job #2713196)

Utilizator Florinos123Gaina Florin Florinos123 Data 27 februarie 2021 13:50:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 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)
{
    return s - 'A' + 1;
}

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

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

    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 ++, sol[k] = i;
        }

        if (i + m < n)
        {
            t -= Val(txt[i]);
            t += Val(txt[i+m]);
        }
    }

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

    return 0;
}