Pagini recente » Cod sursa (job #2015163) | Cod sursa (job #2411537) | Monitorul de evaluare | Cod sursa (job #1259812) | Cod sursa (job #2198714)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int q, k, contor, j, prev2[2000004], i, total, sol[2000004];
char v[2000004], t[2000004];
int main()
{
cin >> v >> t;
contor = strlen(v);
for(i=1; i < contor; i++)
{
if(i == contor-1)
{
i++;
i--;
}
//if(v[j] != v[i] && j > 0)
//j--;
while(v[j] != v[i] && j != 0)
j = prev2[j-1];
if(v[j] == v[i])
prev2[i] = j+1;
else
prev2[i] = 0;
j++;
}
// for(int i=0; i < contor; i++)
// cout << prev2[i] << ' ';
// cout << "\n\n";
q = strlen(t);
j = 0;
for(int i=0; i < q; i++)
{
while(t[i] != v[j] && j > 0)
j = prev2[j-1];
if(t[i] == v[j])
j++;
if(j == contor)
{
total++;
sol[total] = i-contor+1;
}
}
cout << total << '\n';
for(int i=1; i <= total; i++)
cout << sol[i] << ' ';
}