Cod sursa(job #2284057)

Utilizator DariusDCDarius Capolna DariusDC Data 16 noiembrie 2018 18:23:51
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

char text[2000000];
char pattern[1999999];
int PatternSuf[2000000];
int poz[10000];

int main()
{
    fin >> pattern;
    fin >> text;
    int i = 0;
    int j;
    int nr = 0;
    int LungimeText = strlen(text);
    PatternSuf[1] = 0;
    int lungPattern = strlen(pattern);
    for (j = 1; j < lungPattern;j++)
    {
        while (i>0 && pattern[i] != pattern[j])
            i = PatternSuf[i];
        if (pattern[i] == pattern[j])
            i++;
        PatternSuf[j] = i;
    }
    i = 0;
    for (j=0;j<LungimeText;j++)
    {
        while (text[j] != pattern[i] && i>0)
            i = PatternSuf[i];
        if (text[j] == pattern[i])
            i++;
        if (i == lungPattern)
        {
            nr++;
            poz[nr] = j-i+1;
            j = j-i+2;
            i = PatternSuf[i];
        }

    }
    fout << nr << "\n";
    for (int i=1;i<=nr;i++)
        fout << poz[i] << " ";
    return 0;
}