Cod sursa(job #1808437)

Utilizator DanFodorFODOR Dan Horatiu DanFodor Data 17 noiembrie 2016 18:06:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 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
        {
            k = 0;
        }
 
        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);
 
    queue<int> pos;
    int counter = 0;
    int j = 0, start;
 
    for (int i = 0; i < n; ++i)
    {
        start = i;
        while (i < n && j < m && strB[i] == strA[j])
        {
            ++i;
            ++j;
        }
        if (j == m)
        {
            pos.push(start);
            ++counter;
            j = 0;
            i = start;
        }
        else
        {
            if (j > 0)
            {
                i = start + pref[j - 1];
                j = 0;
            }
            else
            {
                i = start;
            }
        }
    }
 
    cout << counter << "\n";

    int total = 0;
    while (!pos.empty() && total < 1000)
    {
        cout << pos.front() << " ";
        pos.pop();
        ++total;
    }
 
    return 0;
}