Cod sursa(job #2002901)

Utilizator CMCmasterCatalin Costescu CMCmaster Data 21 iulie 2017 10:22:31
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

char a[2000002],b[2000002];
int p[2000000];

int main()
{
    in>>a>>b;

    int i = 1,j = 0;
    while(b[i] > 0)
    {
        if(b[i] == b[j])
        {
            p[i] = p[j] + 1;
            i++;
            j++;
        }
        else
        {
            j = p[j - 1];
            if(p[j] == 0)
                i++;
        }
    }

    vector<int> r;

    int n;
    for(n = 0; a[n] > 0;n++);

    j = 0;
    for(i=0;b[i]>0;i++)
    {
        while(j > 0 && a[j] != b[i])
            j = p[j - 1];
        if(a[j] == b[i])
            j++;
        if(j == n - 1)
            r.push_back(i - n + 2);
    }

    n = r.size();
    out<<n<<'\n';
    for(i=0;i<n;i++)
        out<<r[i]<<' ';

    return 0;
}