Cod sursa(job #1211349)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 22 iulie 2014 14:20:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int v[2000001],p[1000];

int main()
{
    int a,b,k = 0,poz = -1;
    string A;
    f >> A;
    A.insert(0, "a");
    a = A.size() - 1;
    string B;
    f >> B;
    B.insert(0, "a");
    b = B.size() - 1;
    for(int i = 2; i <= a; i++){
        while(k > 0 && A[k + 1] != A[i])
            k = v[k];
        if(A[k + 1] == A[i])
           k++;
        v[i] = k;
    }
    k = 0;
    for(int i = 1; i <= b && poz != 1000; i++){
        while(k > 0 && A[k + 1] != B[i])
            k = v[k];
        if(A[k + 1] == B[i])
            k++;
        if(k == a){
            poz++;
            p[poz] = i - a;
        }
    }
    g << poz + 1 << "\n";
    for(int i = 0; i <= poz; i++)
        g << p[i] << " ";
    return 0;
}