Cod sursa(job #3193843)

Utilizator octavi26octavian octavi26 Data 15 ianuarie 2024 20:46:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
#define N 2000008

using namespace std;

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

int n;
char text[N], pattern[N];
int v[N];

void Citire()
{
    fin >> pattern;
    fin >> text;
    n = strlen(pattern);
}

void Precalculare()
{
    int i, j;
    j = 0, i = 1;
    while( i <= n )
    {
        if( pattern[j] == pattern[i] )
        {
            v[i] = j + 1;
            i++;
            j++;
        }
        else{
            if( j == 0 ) {v[i] = 0; i++; continue;}
            j = v[j - 1];
        }
    }
}

int k, sol[N];

void Rezolvare()
{
    int i, j;
    i = j = 0;
    while( text[i] )
    {
        if( text[i] == pattern[j] ) j++, i++;
        else{
            if( j == 0 ) {i++; continue;}
            j = v[j - 1];
        }

        if( j == n )
            sol[++k] = i - n;
    }

    fout << k << "\n";
    for( i=1; i<=min(k, 1000); i++ )
        fout << sol[i] << " ";
}

int main()
{
    Citire();
    Precalculare();
    Rezolvare();
    return 0;
}