Cod sursa(job #2480865)

Utilizator andreigaliAndrei Galitianu andreigali Data 26 octombrie 2019 10:44:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

const int MAXN = 2000041;
char a[MAXN], b[MAXN];
int v[MAXN], p[1004];

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

    int i, j, c=0, k=0;

    fin.getline(a+1, MAXN);
    fin.getline(b+1, MAXN);
    int n, m;
    n = strlen(a+1);
    m = strlen(b+1);

    j=0;
    for(i=2; i<=n; i++)
    {
        while(j!=0 && a[i]!=a[j+1])
        {
            j = v[j];
        }
        if(a[i]==a[j+1])
            j++;
        v[i] = j;
    }
    j=0;
    for(i=1; i<=m; i++)
    {
        while(b[i]!=a[j+1]&&j!=0)
            j = v[j];

        if(b[i]==a[j+1])
            j++;
        if(j==strlen(a+1))
        {
            if(k<1000)
                p[k++] = i-n;
            c++;
        }
    }

    fout << c << "\n";
    for(i=0; i<k; i++)
        fout << p[i] << " ";
    return 0;
}