Pagini recente » Cod sursa (job #596103) | Cod sursa (job #696026) | Cod sursa (job #2480778) | Cod sursa (job #1236562) | Cod sursa (job #2591918)
#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
using namespace std;
const int MMAX = 2000000;
int urm[MMAX + 5];
string t , p;
vector <int> ans;
int main()
{
freopen("strmatch.in" , "r" , stdin);
freopen("strmatch.out" , "w" , stdout);
int n , m , i , k;
getline(cin , p);
getline(cin , t);
n = t.length();
m = p.length();
k = -1;
urm[0] = 0;
for(i = 1 ; i < m ; i ++)
{
while(k > 0 && p[k + 1] != p[i])
k = urm[k];
if(p[k + 1] == p[i])
k ++;
urm[i] = k;
}
k = -1;
for(i = 0 ; i < n ; i ++)
{
while(k > 0 && p[k + 1] != t[i])
k = urm[k];
if(p[k + 1] == t[i])
k ++;
if(k == m - 1)
{
ans.push_back(i - m + 1);
k = urm[k];
}
}
printf("%d\n" , ans.size());
for(i = 0 ; i < ans.size() ; i ++)
printf("%d " , ans[i]);
return 0;
}