Cod sursa(job #1211357)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 22 iulie 2014 14:33:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 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; i++){
        while(k > 0 && A[k + 1] != B[i])
            k = v[k];
        if(A[k + 1] == B[i])
            k++;
        if(k == a){
            poz++;
            if(poz != 1000)
                p[poz] = i - a;
        }
    }
    g << poz + 1 << "\n";
    if(poz < 1000)
        for(int i = 0; i <= poz; i++)
            g << p[i] << " ";
    else
        for(int i = 0; i <= 999; i++)
            g << p[i] << " ";
    return 0;
}