Cod sursa(job #2283528)

Utilizator DariusDCDarius Capolna DariusDC Data 15 noiembrie 2018 16:42:31
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 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 = 1;
    int nr = 0;
    int LungimeText = strlen(text);
    PatternSuf[1] = 0;
    int NTable = strlen(pattern);
    for (j = 1; j < NTable;j++)
    {
        while (i>0 && pattern[i] != pattern[j])
            i = PatternSuf[i];
        if (pattern[i] == pattern[j])
            i++;
        PatternSuf[j] = i;
    }
    i = 0;
    j = 0;
    while (j<=LungimeText)
    {
        while (pattern[i] != text[j] && i>0)
        {
            i = PatternSuf[i];
        }
        if (pattern[i] == text[j])
            i++;
        if (i==NTable)
        {
            nr++;
            poz[nr] = j - i + 1;
            i = PatternSuf[i-1];
        }
        j++;

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