Cod sursa(job #1808432)

Utilizator DanFodorFODOR Dan Horatiu DanFodor Data 17 noiembrie 2016 18:05:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <queue>
 
using namespace std;
 
void compute_pref(int *pref, string &str, int len)
{
    pref[0] = 0;
    int k = 0;
    for (int i = 1; i < len; ++i)
    {
        if (str[k] == str[i])
        {
            ++k;
        }
        else
        {
            while (k > 0 && str[k] != str[i])
                k = pref[k-1];
            if (str[k] == str[i])
                ++k;
        }
 
        pref[i] = k;
    }
}
 
int main()
{
    ifstream cin ("strmatch.in");
    ofstream cout ("strmatch.out");
 
    string strA;
    string strB;
 
    cin >> strA;
    cin >> strB;
 
    int m = strA.length();
    int n = strB.length();
 
    int pref[m];
    compute_pref(pref, strA, m);
 
    
    /*for (int i = 0; i < m; ++i)
    {
        cout << pref[i] << " ";
    }*/
    

    queue<int> pos;
    int counter = 0;
    int j = 0;
 
    for (int i = 0; i < n; ++i)
    {
        while (i < n && j < m && strB[i] == strA[j])
        {
            ++i;
            ++j;
        }
        if (j == m)
        {
            pos.push(i-m);
            ++counter;
            j = pref[j-1];
            --i;
        }
        else
        {
            if (j > 0)
            {
                j = pref[j - 1];
                --i;
            }
        }
    }
    
    cout << counter << "\n";
    int displayed = 0;
    while (!pos.empty() && displayed < 1000)
    {
        cout << pos.front() << " ";
        pos.pop();
        ++displayed;
    }
 
    return 0;
}